oj.uz

Submission #331420

# Submission time Handle Problem Language Result Execution time Memory
331420 2020-11-28T12:23:00 Z EIMONIM Examination (JOI19_examination) C++14
100 / 100
 2783 ms 327020 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};
        //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.lower_bound(a[i])->second, b[i] = convt.lower_bound(b[i])->second;
    //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);
            bit.add(s[i], t[i]);
        }
        else{ // query
            i-=n;
            //ams [i] = seg.query(a[i], MAXX, b[i], MAXY, 0, MAXX);
            ans[i] = bit.qry(a[i], b[i]);
        }
    }
    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 48 ms 42604 KB Output is correct
4 Correct 46 ms 42604 KB Output is correct
5 Correct 48 ms 42604 KB Output is correct
6 Correct 47 ms 42604 KB Output is correct
7 Correct 85 ms 48108 KB Output is correct
8 Correct 86 ms 48108 KB Output is correct
9 Correct 85 ms 48236 KB Output is correct
10 Correct 80 ms 44908 KB Output is correct
11 Correct 76 ms 45056 KB Output is correct
12 Correct 69 ms 42732 KB Output is correct
13 Correct 82 ms 48236 KB Output is correct
14 Correct 85 ms 48236 KB Output is correct
15 Correct 83 ms 48364 KB Output is correct
16 Correct 70 ms 45184 KB Output is correct
17 Correct 92 ms 44908 KB Output is correct
18 Correct 72 ms 42732 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2267 ms 285048 KB Output is correct
2 Correct 2326 ms 285040 KB Output is correct
3 Correct 2254 ms 284528 KB Output is correct
4 Correct 1016 ms 91756 KB Output is correct
5 Correct 690 ms 87424 KB Output is correct
6 Correct 929 ms 47084 KB Output is correct
7 Correct 2107 ms 266352 KB Output is correct
8 Correct 2264 ms 264296 KB Output is correct
9 Correct 1949 ms 234868 KB Output is correct
10 Correct 670 ms 78568 KB Output is correct
11 Correct 918 ms 91620 KB Output is correct
12 Correct 985 ms 46828 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2267 ms 285048 KB Output is correct
2 Correct 2326 ms 285040 KB Output is correct
3 Correct 2254 ms 284528 KB Output is correct
4 Correct 1016 ms 91756 KB Output is correct
5 Correct 690 ms 87424 KB Output is correct
6 Correct 929 ms 47084 KB Output is correct
7 Correct 2107 ms 266352 KB Output is correct
8 Correct 2264 ms 264296 KB Output is correct
9 Correct 1949 ms 234868 KB Output is correct
10 Correct 670 ms 78568 KB Output is correct
11 Correct 918 ms 91620 KB Output is correct
12 Correct 985 ms 46828 KB Output is correct
13 Correct 2344 ms 284868 KB Output is correct
14 Correct 2284 ms 284772 KB Output is correct
15 Correct 2211 ms 284924 KB Output is correct
16 Correct 1072 ms 93292 KB Output is correct
17 Correct 730 ms 89872 KB Output is correct
18 Correct 997 ms 47212 KB Output is correct
19 Correct 2393 ms 284408 KB Output is correct
20 Correct 2339 ms 284528 KB Output is correct
21 Correct 2282 ms 274520 KB Output is correct
22 Correct 647 ms 78612 KB Output is correct
23 Correct 937 ms 91500 KB Output is correct
24 Correct 1026 ms 46956 KB Output is correct

Subtask #4
57.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 48 ms 42604 KB Output is correct
4 Correct 46 ms 42604 KB Output is correct
5 Correct 48 ms 42604 KB Output is correct
6 Correct 47 ms 42604 KB Output is correct
7 Correct 85 ms 48108 KB Output is correct
8 Correct 86 ms 48108 KB Output is correct
9 Correct 85 ms 48236 KB Output is correct
10 Correct 80 ms 44908 KB Output is correct
11 Correct 76 ms 45056 KB Output is correct
12 Correct 69 ms 42732 KB Output is correct
13 Correct 82 ms 48236 KB Output is correct
14 Correct 85 ms 48236 KB Output is correct
15 Correct 83 ms 48364 KB Output is correct
16 Correct 70 ms 45184 KB Output is correct
17 Correct 92 ms 44908 KB Output is correct
18 Correct 72 ms 42732 KB Output is correct
19 Correct 2267 ms 285048 KB Output is correct
20 Correct 2326 ms 285040 KB Output is correct
21 Correct 2254 ms 284528 KB Output is correct
22 Correct 1016 ms 91756 KB Output is correct
23 Correct 690 ms 87424 KB Output is correct
24 Correct 929 ms 47084 KB Output is correct
25 Correct 2107 ms 266352 KB Output is correct
26 Correct 2264 ms 264296 KB Output is correct
27 Correct 1949 ms 234868 KB Output is correct
28 Correct 670 ms 78568 KB Output is correct
29 Correct 918 ms 91620 KB Output is correct
30 Correct 985 ms 46828 KB Output is correct
31 Correct 2344 ms 284868 KB Output is correct
32 Correct 2284 ms 284772 KB Output is correct
33 Correct 2211 ms 284924 KB Output is correct
34 Correct 1072 ms 93292 KB Output is correct
35 Correct 730 ms 89872 KB Output is correct
36 Correct 997 ms 47212 KB Output is correct
37 Correct 2393 ms 284408 KB Output is correct
38 Correct 2339 ms 284528 KB Output is correct
39 Correct 2282 ms 274520 KB Output is correct
40 Correct 647 ms 78612 KB Output is correct
41 Correct 937 ms 91500 KB Output is correct
42 Correct 1026 ms 46956 KB Output is correct
43 Correct 2760 ms 320532 KB Output is correct
44 Correct 2783 ms 325228 KB Output is correct
45 Correct 2689 ms 327020 KB Output is correct
46 Correct 1087 ms 121836 KB Output is correct
47 Correct 838 ms 122512 KB Output is correct
48 Correct 974 ms 47980 KB Output is correct
49 Correct 2550 ms 302272 KB Output is correct
50 Correct 2576 ms 305068 KB Output is correct
51 Correct 2378 ms 267604 KB Output is correct
52 Correct 948 ms 114060 KB Output is correct
53 Correct 959 ms 120300 KB Output is correct