I did it in order higher than the main solution in the D problem and became TLE in Python, so I made it C ++ and speeded it up. This solution is also an important idea, so I would like to learn it.
All you have to do is move the road to the end.
answerA.py
a,b=map(int,input().split())
print((a-1)*(b-1))
Since there are 8 divisors, we will count them using the divisor enumeration function in this article. If you only have how many, you can calculate without preparing an array.
answerB.py
def make_divisors(n):
divisors=[]
for i in range(1,int(n**0.5)+1):
if n%i==0:
divisors.append(i)
if i!=n//i:
divisors.append(n//i)
return divisors
ans=0
n=int(input())
for i in range(1,n+1):
ans+=(len(make_divisors(i))==8 and i%2==1)
print(ans)
Since the subject is operated on the character string 5000 trillion times, each number $ x (\ neq1) $ included in the character string becomes $ x ^ {5000000000000000} $ after 5000 trillion times, so ** $ You can see that it is clearly longer than K $ **. Therefore, if the first character is a character other than 1, you can see that the $ K $ character is $ x $. Similarly, assuming that 1s are consecutive from the 1st character to the $ l $ character, if it is $ l \ geqq K $, the K character will be 1. Conversely, if $ l <K $, the K character is the l + 1 character number.
answerC.py
s=input()
k=int(input())
l=0
for i in s:
if i=="1":
l+=1
else:
break
print("1" if k<=l else s[l])
Since the question query asks the interval repeatedly (up to $ 10 ^ 5 $ times), we know that we want to speed up the calculation of the interval here. Therefore, we will consider how to calculate up to $ 10 ^ 3 $ for each query.
Here, when the number of trains passing through the section [$ l, r $] is $ x_ {l, r} $, the trains passing through the section from city $ p_i $ to city $ q_i $. The number of is $ (x_ {p_i, p_i} + x_ {p_i, p_i + 1} +… + x_ {p_i, q_i}) + (x_ {p_i + 1, p_i + 1} +… + x_ {p_i + 1 , q_i}) +… + (x_ {q_i, q_i}) = \ Sigma_ {k = p_i} ^ {q_i} {(\ Sigma_ {l = k} ^ {q_i} {x_ {k, l}})} Since it will be $ (✳︎), I thought that $ k $ (** left end of the section **) should be fixed.
Therefore, when the section through which each train passes is first given in the form of [$ L_i, R_i $], prepare a two-dimensional array train in which the left end of the section is divided by which city, and the $ L_i $ th. Insert the rightmost value $ R_i $ into the array of. Then, after all the insertions, sort each array. Under this, when $ p_i $ and $ q_i $ are given in each question query, ** $ p_i $ th array to $ q_i $ th array (up to N ways) **, respectively ** Just count the number of elements under $ q_i $ ** (∵ (✳︎)). You can do a binary search ($ O (\ log {M}) $) on each ** (sorted) array ** to count how many elements there are. Therefore, the total complexity is $ O (QN log {M}) $. (First and second code, AC for C ++, TLE for Python and PyPy)
Also, if the prepared two-dimensional array train is ** train [$ i
Also, the following code uses bisect_right for binary search. See this article for more information.
answerD_TLE.py
import bisect
n,m,q=map(int,input().split())
train=[[] for i in range(n)]
for i in range(m):
l,r=map(int,input().split())
train[l-1].append(r-1)
for i in range(n):
train[i].sort()
for i in range(q):
p,q=map(int,input().split())
ans=0
for i in range(p-1,q):
ans+=bisect.bisect_right(train[i],q-1)
print(ans)
answerD.cc
//Reference: http://ehafib.hatenablog.com/entry/2015/12/23/164517
//Include(Alphabetical order,bits/stdc++.Factions that do not use h)
#include<algorithm>//sort,Binary search,Such
#include<bitset>//Fixed length bit set
#include<cmath>//pow,log etc.
#include<complex>//Complex number
#include<deque>//Queue for double-ended access
#include<functional>//sort greater
#include<iomanip>//setprecision(Floating point output error)
#include<iostream>//Input / output
#include<iterator>//Set arithmetic(Intersection,Union,Difference set, etc.)
#include<map>//map(dictionary)
#include<numeric>//iota(Generation of integer sequence),gcd and lcm(c++17)
#include<queue>//queue
#include<set>//set
#include<stack>//stack
#include<string>//String
#include<unordered_map>//Map with iterator but not keeping order
#include<unordered_set>//Set with iterator but not keeping order
#include<utility>//pair
#include<vector>//Variable length array
using namespace std;
typedef long long ll;
//macro
//for loop relationship
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of ends)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 1.
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//x is a container such as vector
#define ALL(x) (x).begin(),(x).end() //I want to omit arguments such as sort
#define SIZE(x) ((ll)(x).size()) //size to size_Change from t to ll
#define MAX(x) *max_element(ALL(x)) //Find the maximum value
#define MIN(x) *min_element(ALL(x)) //Find the minimum value
#define D()
//constant
#define INF 1000000000000 //10^12:Extremely large value,∞
#define MOD 10000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array(Used for prime number enumeration etc.)
//Abbreviation
#define PB push_back //Insert into vector
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair
//↑ Templates from here to above
signed main(){
ll n,m,q;cin >> n >> m >> q;
vector<vector<ll>> train(n);
REP(i,m){
ll l,r;cin >> l >> r;
train[l-1].PB(r-1);
}
REP(i,n){
sort(ALL(train[i]));
}
REP(i,q){
ll p,q_;cin >> p >> q_;
ll ans=0;
FOR(j,p-1,q_-1){
ans+=ll(upper_bound(ALL(train[j]),q_-1)-train[j].begin());
}
cout << ans << endl;
}
}
answerD.py
n,m,q=map(int,input().split())
train=[[0]*n for i in range(n)]
for i in range(m):
l,r=map(int,input().split())
train[l-1][r-1]+=1
for i in range(n):
for j in range(n-1):
train[i][j+1]+=train[i][j]
for i in range(q):
p,q_=map(int,input().split())
ans=0
for j in range(p-1,q_):
ans+=train[j][q_-1]
print(ans)
Recommended Posts