Time required

Impressions

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.

Problem A

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))

B problem

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)

C problem

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])

D problem

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 ] [ j ]: the number of trains whose section is [ i, j ] **, then [ L_i, R_i ] ], By adding +1 to train [ L_i ] [ R_i $] and considering the cumulative sum, the question query does not perform a binary search for how many elements are under $ q_i $. Since it can be calculated by ** $ O (1) $ **, the amount of calculation is O ($ QN + N ^ 2 $). (Third code, AC with PyPy)

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)

[PYTHON] AtCoder Beginner Contest 106 Review of past questions

Time required

Impressions

Problem A

answerA.py

B problem

answerB.py

C problem

answerC.py