oj.uz

Submission #257210

# Submission time Handle Problem Language Result Execution time Memory
257210 2020-08-03T21:01:45 Z infinitepro Examination (JOI19_examination) C++17
41 / 100
 2944 ms 143580 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_equal<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 1 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 2795 ms 143360 KB Output is correct
2 Correct 2453 ms 143396 KB Output is correct
3 Correct 2586 ms 143580 KB Output is correct
4 Correct 1753 ms 143296 KB Output is correct
5 Correct 673 ms 38880 KB Output is correct
6 Correct 598 ms 38904 KB Output is correct
7 Correct 2782 ms 143404 KB Output is correct
8 Correct 2303 ms 143352 KB Output is correct
9 Correct 2125 ms 143352 KB Output is correct
10 Correct 429 ms 31224 KB Output is correct
11 Correct 1308 ms 143224 KB Output is correct
12 Correct 542 ms 31096 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2795 ms 143360 KB Output is correct
2 Correct 2453 ms 143396 KB Output is correct
3 Correct 2586 ms 143580 KB Output is correct
4 Correct 1753 ms 143296 KB Output is correct
5 Correct 673 ms 38880 KB Output is correct
6 Correct 598 ms 38904 KB Output is correct
7 Correct 2782 ms 143404 KB Output is correct
8 Correct 2303 ms 143352 KB Output is correct
9 Correct 2125 ms 143352 KB Output is correct
10 Correct 429 ms 31224 KB Output is correct
11 Correct 1308 ms 143224 KB Output is correct
12 Correct 542 ms 31096 KB Output is correct
13 Correct 2406 ms 143356 KB Output is correct
14 Correct 2624 ms 143356 KB Output is correct
15 Correct 2944 ms 143352 KB Output is correct
16 Correct 1582 ms 143480 KB Output is correct
17 Correct 644 ms 39032 KB Output is correct
18 Correct 571 ms 39160 KB Output is correct
19 Correct 2441 ms 143504 KB Output is correct
20 Correct 2579 ms 143564 KB Output is correct
21 Correct 2101 ms 143352 KB Output is correct
22 Correct 407 ms 31224 KB Output is correct
23 Correct 1522 ms 143120 KB Output is correct
24 Correct 562 ms 31208 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 1 ms 384 KB Output is correct
5 Incorrect 0 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -