oj.uz

Submission #331419

# Submission time Handle Problem Language Result Execution time Memory
331419 2020-11-28T12:20:28 Z EIMONIM Examination (JOI19_examination) C++14
43 / 100
 3000 ms 374852 KB 
#include <bits/stdc++.h>
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1;i>=s;i--)
using namespace std;
const int INF = 1e9, MOD = 1e9 + 7;

int MAXX = 0, MAXY = 0;
struct Node{
    int v=0;
    Node *lp=0, *rp=0;
    Node(){}
    void fix(){
        if (!lp) lp = new Node();
        if (!rp) rp = new Node();
    }
    void update(int i, int dx, int l, int r){
        if (r<=l) return ;
        if (l+1==r){
            v+=dx;
            return ;
        }
        int mid = (l+r)/2;
        fix();
        if (i<mid) lp->update(i,dx,l,mid);
        else rp->update(i,dx,mid,r);
        //cout<<"UPDATE1: "<<i<<" "<<l<<" "<<r<<(v - lp->v - rp->v)<<endl;
        v = lp->v + rp->v;
    }
    int query(int a, int b, int l, int r){
        if (a>r || b<l) return 0;
        //cout<<"QUERY1: "<<a<<" "<<v<<" "<<l<<" "<<r<<endl;
        if (a<=l && r<=b) return v;
        int res = 0, mid = (l+r)/2;
        if (lp) res += lp->query(a,b,l,mid);
        if (rp) res += rp->query(a,b,mid,r);
        return res;
    }
};
struct Node2d{
    Node seg;
    Node2d *lp=0, *rp=0;
    Node2d(){}
    void fix(){
        if (!lp) lp = new Node2d();
        if (!rp) rp = new Node2d();
    }
    void update(int i, int j, int dx, int l, int r){
        if (r<=l) return ;
        //cout<<"UPDATE: "<<i<<" "<<j<<" "<<l<<" "<<r<<endl;
        seg.update(j, dx, 0, MAXY);
        if (l+1==r) return ;
        int mid = (l+r)/2;
        fix();
        if (i<mid) lp->update(i,j,dx,l,mid);
        else rp->update(i,j,dx,mid,r);
    }
    int query(int ax, int bx, int ay, int by, int l, int r){
        if (ax>r || bx<l) return 0;
        if (ax<=l && r<=bx) {
            int v = seg.query(ay, by, 0, MAXY);
            //cout<<"QUERY: "<<ax<<" "<<ay<<" "<<l<<" "<<r<<" "<<v<<endl;
            return v;
        }
        int res = 0, mid = (l+r)/2;
        if (lp) res += lp->query(ax,bx,ay,by,l,mid);
        if (rp) res += rp->query(ax,bx,ay,by,mid,r);
        return res;
    }
};
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
const int RANDOM =
    chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
  int operator()(int x) const { return x ^ RANDOM; }
};
struct sparsebit {
  const int MAX = 2e5+10;
  vector<gp_hash_table<int, int, chash>> fen;
  sparsebit(): fen(MAX+1){}
  int tot = 0;
  void add(int x, int y) {
    // debug("in upd");
    tot++;
    for (int i = x; i <= MAX; i += (i & -i)) {
      for (int j = y; j <= MAX; j += (j & -j)) {
        // debug(i, j, 1);
        // cnt++;
        fen[i][j] ++;
      }
    }
    // debug("out upd");
  }
 
  int qry(int x, int y) {
    int ret = 0;
    for (int i = x; i > 0; i -= (i & -i)) {
      for (int j = y; j > 0; j -= (j & -j)) {
        // cnt++;
        ret += fen[i][j];
      }
    }
    return ret;
  }
 
  int qry(int a, int b, int c, int d) {
    // debug("in big qry");
    int ret = tot;
    if (a) ret -= qry(a - 1, d);
    if (b) ret -= qry(c, b - 1);
    if (a && b) ret += qry(a - 1, b - 1);
    // debug("out big qry");
    return ret;
  }
 
  void init() { fen.resize(MAX + 1); }
};
bool cmp(pair<int, int> a, pair<int, int> b){
    return (a.first==b.first?a.second<b.second:a.first>b.first);
}
const int MAXN = 1e5 + 10;
int s[MAXN], t[MAXN];
int a[MAXN], b[MAXN], c[MAXN];
int ans[MAXN];
pair<int, int> vals[2*MAXN];
int32_t main(){
    ios_base::sync_with_stdio(false);
    int n,q; cin>>n>>q;
    map<int, int> convs, convt;
    loop(i,0,n){
        cin>>s[i]>>t[i];
        vals[i] = {s[i]+t[i], i};
        convs[s[i]];
        convt[t[i]];
        //MAXX = max(MAXX, s[i]);
        //MAXY = max(MAXY, t[i]);
    }
    loop(i,0,q){
        cin>>a[i]>>b[i]>>c[i];
        vals[i+n] = {c[i], n+i};
        convs[a[i]];
        convt[b[i]];
        //MAXX = max(MAXX, a[i]);
        //MAXY = max(MAXY, b[i]);
    }
    sort(vals, vals+n+q, cmp);
    //MAXX++, MAXY++;
    int cnt = 0;
    for(auto &p:convs) p.second = cnt++;
    for(auto &p:convs) p.second = cnt - p.second;
    MAXX = cnt;
    cnt = 0;
    for(auto &p:convt) p.second = cnt++;
    for(auto &p:convt) p.second = cnt - p.second;
    MAXY = cnt;
    loop(i,0,n) s[i] = convs[s[i]], t[i] = convt[t[i]];
    loop(i,0,q) a[i] = convs[a[i]], b[i] = convt[b[i]];
    //Node2d seg;
    sparsebit bit;
    loop(ind, 0, n+q){
        int i = vals[ind].second;
        //cout<<"VALS: "<<vals[ind].first<<" "<<i<<" "<<i-n<<endl;
        if (i<n){ // point
            //seg.update(s[i], t[i], 1, 0, MAXX);
            //cout<<"HI: " <<s[i]<<" "<<t[i]<<endl;
            bit.add(s[i], t[i]);
        }
        else{ // query
            i-=n;
            ans[i] = bit.qry(a[i], b[i]);
            //seg.query(a[i], MAXX, b[i], MAXY, 0, MAXX);
        }
    }
    loop(i,0,q) cout<<ans[i]<<endl;
    return 0;
}
/*
color a
cls
g++ Examination.cpp -o a & a
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100





*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 42604 KB Output is correct
2 Correct 47 ms 42604 KB Output is correct
3 Correct 56 ms 42752 KB Output is correct
4 Correct 47 ms 42604 KB Output is correct
5 Correct 47 ms 42732 KB Output is correct
6 Correct 46 ms 42604 KB Output is correct
7 Correct 97 ms 50156 KB Output is correct
8 Correct 95 ms 49388 KB Output is correct
9 Correct 97 ms 49644 KB Output is correct
10 Correct 81 ms 46060 KB Output is correct
11 Correct 74 ms 45440 KB Output is correct
12 Correct 74 ms 42860 KB Output is correct
13 Correct 92 ms 49900 KB Output is correct
14 Correct 95 ms 50156 KB Output is correct
15 Correct 100 ms 49516 KB Output is correct
16 Correct 79 ms 45164 KB Output is correct
17 Correct 80 ms 46208 KB Output is correct
18 Correct 72 ms 42860 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2688 ms 309592 KB Output is correct
2 Correct 2691 ms 312316 KB Output is correct
3 Correct 2697 ms 312024 KB Output is correct
4 Correct 1186 ms 103276 KB Output is correct
5 Correct 804 ms 114224 KB Output is correct
6 Correct 939 ms 48364 KB Output is correct
7 Correct 2372 ms 293544 KB Output is correct
8 Correct 2566 ms 290160 KB Output is correct
9 Correct 2110 ms 253952 KB Output is correct
10 Correct 758 ms 108388 KB Output is correct
11 Correct 1008 ms 104172 KB Output is correct
12 Correct 790 ms 47852 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2688 ms 309592 KB Output is correct
2 Correct 2691 ms 312316 KB Output is correct
3 Correct 2697 ms 312024 KB Output is correct
4 Correct 1186 ms 103276 KB Output is correct
5 Correct 804 ms 114224 KB Output is correct
6 Correct 939 ms 48364 KB Output is correct
7 Correct 2372 ms 293544 KB Output is correct
8 Correct 2566 ms 290160 KB Output is correct
9 Correct 2110 ms 253952 KB Output is correct
10 Correct 758 ms 108388 KB Output is correct
11 Correct 1008 ms 104172 KB Output is correct
12 Correct 790 ms 47852 KB Output is correct
13 Correct 2746 ms 312512 KB Output is correct
14 Correct 2691 ms 314184 KB Output is correct
15 Correct 2617 ms 313940 KB Output is correct
16 Correct 1138 ms 105196 KB Output is correct
17 Correct 842 ms 118856 KB Output is correct
18 Correct 845 ms 48108 KB Output is correct
19 Correct 2760 ms 313800 KB Output is correct
20 Correct 2758 ms 312872 KB Output is correct
21 Correct 2629 ms 305952 KB Output is correct
22 Correct 748 ms 108412 KB Output is correct
23 Correct 1024 ms 104044 KB Output is correct
24 Correct 753 ms 47724 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 42604 KB Output is correct
2 Correct 47 ms 42604 KB Output is correct
3 Correct 56 ms 42752 KB Output is correct
4 Correct 47 ms 42604 KB Output is correct
5 Correct 47 ms 42732 KB Output is correct
6 Correct 46 ms 42604 KB Output is correct
7 Correct 97 ms 50156 KB Output is correct
8 Correct 95 ms 49388 KB Output is correct
9 Correct 97 ms 49644 KB Output is correct
10 Correct 81 ms 46060 KB Output is correct
11 Correct 74 ms 45440 KB Output is correct
12 Correct 74 ms 42860 KB Output is correct
13 Correct 92 ms 49900 KB Output is correct
14 Correct 95 ms 50156 KB Output is correct
15 Correct 100 ms 49516 KB Output is correct
16 Correct 79 ms 45164 KB Output is correct
17 Correct 80 ms 46208 KB Output is correct
18 Correct 72 ms 42860 KB Output is correct
19 Correct 2688 ms 309592 KB Output is correct
20 Correct 2691 ms 312316 KB Output is correct
21 Correct 2697 ms 312024 KB Output is correct
22 Correct 1186 ms 103276 KB Output is correct
23 Correct 804 ms 114224 KB Output is correct
24 Correct 939 ms 48364 KB Output is correct
25 Correct 2372 ms 293544 KB Output is correct
26 Correct 2566 ms 290160 KB Output is correct
27 Correct 2110 ms 253952 KB Output is correct
28 Correct 758 ms 108388 KB Output is correct
29 Correct 1008 ms 104172 KB Output is correct
30 Correct 790 ms 47852 KB Output is correct
31 Correct 2746 ms 312512 KB Output is correct
32 Correct 2691 ms 314184 KB Output is correct
33 Correct 2617 ms 313940 KB Output is correct
34 Correct 1138 ms 105196 KB Output is correct
35 Correct 842 ms 118856 KB Output is correct
36 Correct 845 ms 48108 KB Output is correct
37 Correct 2760 ms 313800 KB Output is correct
38 Correct 2758 ms 312872 KB Output is correct
39 Correct 2629 ms 305952 KB Output is correct
40 Correct 748 ms 108412 KB Output is correct
41 Correct 1024 ms 104044 KB Output is correct
42 Correct 753 ms 47724 KB Output is correct
43 Execution timed out 3096 ms 374852 KB Time limit exceeded
44 Halted 0 ms 0 KB -