oj.uz

Submission #62272

# Submission time Handle Problem Language Result Execution time Memory
62272 2018-07-28T01:10:36 Z Benq Cambridge (info1cup18_cambridge) C++11
100 / 100
 627 ms 33168 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 1<<17;

template<class T, int SZ> struct LazySegTree {
    T sum[2*SZ], mn[2*SZ], lazy[2*SZ]; // set SZ to a power of 2
    
    LazySegTree() {
        memset (sum,0,sizeof sum);
        memset (mn,0,sizeof mn);
        memset (lazy,0,sizeof lazy);
    }
    
    void push(int ind, int L, int R) {
        sum[ind] += (R-L+1)*lazy[ind];
        mn[ind] += lazy[ind];
        if (L != R) lazy[2*ind] += lazy[ind], lazy[2*ind+1] += lazy[ind];
        lazy[ind] = 0;
    }
    
    void pull(int ind) {
        sum[ind] = sum[2*ind]+sum[2*ind+1];
        mn[ind] = min(mn[2*ind],mn[2*ind+1]);
    }
    
    void build() {
        F0Rd(i,SZ) pull(i);
    }
    
    T qsum(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1) {
        push(ind,L,R);
        if (lo > R || L > hi) return 0;
        if (lo <= L && R <= hi) return sum[ind];
        
        int M = (L+R)/2;
        return qsum(lo,hi,2*ind,L,M) + qsum(lo,hi,2*ind+1,M+1,R);
    }

    T qmin(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1) {
        push(ind,L,R);
        if (lo > R || L > hi) return INF;
        if (lo <= L && R <= hi) return mn[ind];
        
        int M = (L+R)/2;
        return min(qmin(lo,hi,2*ind,L,M), qmin(lo,hi,2*ind+1,M+1,R));
    }
    
    void upd(int lo, int hi, ll inc, int ind = 1, int L = 0, int R = SZ-1) {
        push(ind,L,R);
        if (hi < L || R < lo) return;
        if (lo <= L && R <= hi) {
            lazy[ind] = inc;
            push(ind,L,R);
            return;
        }
        
        int M = (L+R)/2;
        upd(lo,hi,inc,2*ind,L,M); upd(lo,hi,inc,2*ind+1,M+1,R);
        pull(ind);
    }
};

LazySegTree<ll,MX> L;

int N,M,key[MX], lst[MX],T[MX],D[MX],ans[MX];
map<pi,int> m;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    FOR(i,1,N+1) {
        cin >> T[i] >> D[i];
        m[{D[i],i}] = 0;
    }
    int co = 0; for (auto& a: m) a.s = co++;
    FOR(i,1,N+1) key[i] = m[{D[i],i}];
    int r = 0;
    L.upd(0,MX-1,MOD);
    FOR(i,1,N+1) {
        while (L.qmin(0,MX-1) > 0 && r <= N) {
            r ++;
            if (r != N+1) {
                L.upd(key[r],key[r],D[r]-MOD);
                L.upd(key[r],MX-1,-T[r]);
            }
        }
        L.upd(key[i],key[i],MOD-D[i]);
        L.upd(key[i],MX-1,T[i]);
        ans[i] = r-1;
    }
    F0R(i,M) {
        int x,y; cin >> x >> y;
        cout << (ans[x] >= y) << "\n";
    }
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6520 KB Output is correct
2 Correct 9 ms 6640 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6520 KB Output is correct
2 Correct 9 ms 6640 KB Output is correct
3 Correct 430 ms 16076 KB Output is correct
4 Correct 11 ms 16076 KB Output is correct
5 Correct 41 ms 16076 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6520 KB Output is correct
2 Correct 9 ms 6640 KB Output is correct
3 Correct 38 ms 16076 KB Output is correct
4 Correct 44 ms 16076 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6520 KB Output is correct
2 Correct 9 ms 6640 KB Output is correct
3 Correct 430 ms 16076 KB Output is correct
4 Correct 11 ms 16076 KB Output is correct
5 Correct 41 ms 16076 KB Output is correct
6 Correct 38 ms 16076 KB Output is correct
7 Correct 44 ms 16076 KB Output is correct
8 Correct 475 ms 20908 KB Output is correct
9 Correct 627 ms 23904 KB Output is correct
10 Correct 431 ms 26880 KB Output is correct
11 Correct 337 ms 30312 KB Output is correct
12 Correct 281 ms 33168 KB Output is correct
13 Correct 10 ms 33168 KB Output is correct