oj.uz

Submission #257209

# Submission time Handle Problem Language Result Execution time Memory
257209 2020-08-03T21:00:22 Z infinitepro Examination (JOI19_examination) C++17
41 / 100
 2619 ms 146520 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_updat

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define int ll

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

typedef tree<ii,null_type,less<ii>,rb_tree_tag,
tree_order_statistics_node_update> ost;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()

class LazyTree{
  //Here    ↓
    int N; vector<ost> st;
    int gpt;
  //Here                                        ↓
    void upd(int v, int l, int r, int L, int R, int d){
        if(r < L or R < l) return;
        // add d into sorted array
        st[v].insert({d, gpt++});
        if(l == r) return;

        int m = (l+r)/2, v1 = 2*v, v2 = v1+1;
        upd(v1, l, m, L, R, d);
        upd(v2, m+1, r, L, R, d);
        return;
    }
  //↓ Here
    int qry(int v, int l, int r, int L, int R, int d){
        if(r < L or R < l) return 0;
        if(L <= l and r <= R){
            int cfvs = st[v].size() - st[v].order_of_key({d, 0});
            return cfvs;
        }
        int m = (l+r)/2, v1 = 2*v, v2 = v1+1;
     //Here                      ↓
        return qry(v1, l, m, L, R, d)+qry(v2, m+1, r, L, R, d);
    }
    public:
        LazyTree(int N){st.resize(4*N);this->N = N; gpt = 1;}
      //Here                   ↓
        void upd(int L, int R, int d){return upd(1, 0, N, L, R, d);}
      //↓ Here
        int qry(int L, int R, int d){return qry(1, 0, N, L, R, d);}
};

struct node1{
    int s, t;
};

struct node2{
    int a, b, c, idx;
};

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q; cin >> n >> q;
    vector<node1> a(n);
    for(auto &i : a) cin >> i.s >> i.t;
    sort(all(a), [](auto a, auto b){return a.s+a.t>b.s+b.t;});

    vector<node2> cpq(q);
    for(int x = 0; x < q; x++){
        cin >> cpq[x].a >> cpq[x].b >> cpq[x].c;
        cpq[x].idx = x;
    }
    sort(all(cpq), [](auto z1, auto z2){return z1.c>z2.c;});

    set<int> ccrowtmp;
    for(int x = 0; x < n; x++){
        ccrowtmp.insert(a[x].s);
    }
    int vcvt = 0;
    map<int, int> ccrow;
    for(auto v : ccrowtmp){
        ccrow[v] = vcvt++;
    }

    int jp = ccrow.size()+5;
    LazyTree ST(jp);

    vi sol(q); int stp = 0;
    for(auto qq : cpq){
        while(stp < n && a[stp].s+a[stp].t >= qq.c){
            // insert into merge segtree
            int xv = (*ccrow.lower_bound(a[stp].s)).second;
            ST.upd(xv, xv, a[stp].t);
            stp++;
        }

        int xv = (*ccrow.lower_bound(qq.a)).second;
        sol[qq.idx] = ST.qry(xv, jp, qq.b);
    }

    for(auto i : sol) cout << i << endl;


    return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Incorrect 0 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2619 ms 143444 KB Output is correct
2 Correct 2493 ms 145700 KB Output is correct
3 Correct 2598 ms 145992 KB Output is correct
4 Correct 1663 ms 145144 KB Output is correct
5 Correct 680 ms 40696 KB Output is correct
6 Correct 587 ms 39928 KB Output is correct
7 Correct 2457 ms 145656 KB Output is correct
8 Correct 2398 ms 145980 KB Output is correct
9 Correct 1998 ms 145708 KB Output is correct
10 Correct 428 ms 33016 KB Output is correct
11 Correct 1340 ms 145144 KB Output is correct
12 Correct 563 ms 32248 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2619 ms 143444 KB Output is correct
2 Correct 2493 ms 145700 KB Output is correct
3 Correct 2598 ms 145992 KB Output is correct
4 Correct 1663 ms 145144 KB Output is correct
5 Correct 680 ms 40696 KB Output is correct
6 Correct 587 ms 39928 KB Output is correct
7 Correct 2457 ms 145656 KB Output is correct
8 Correct 2398 ms 145980 KB Output is correct
9 Correct 1998 ms 145708 KB Output is correct
10 Correct 428 ms 33016 KB Output is correct
11 Correct 1340 ms 145144 KB Output is correct
12 Correct 563 ms 32248 KB Output is correct
13 Correct 2395 ms 146380 KB Output is correct
14 Correct 2595 ms 146520 KB Output is correct
15 Correct 2419 ms 145916 KB Output is correct
16 Correct 1536 ms 145500 KB Output is correct
17 Correct 670 ms 41072 KB Output is correct
18 Correct 626 ms 40056 KB Output is correct
19 Correct 2234 ms 146168 KB Output is correct
20 Correct 2430 ms 146504 KB Output is correct
21 Correct 2098 ms 146296 KB Output is correct
22 Correct 435 ms 33020 KB Output is correct
23 Correct 1359 ms 144876 KB Output is correct
24 Correct 569 ms 32120 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Incorrect 0 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -