oj.uz

Submission #950889

# Submission time Handle Problem Language Result Execution time Memory
950889 2024-03-20T22:20:01 Z idiotcomputer Examination (JOI19_examination) C++11
100 / 100
 1536 ms 91664 KB 
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first 
#define s second 
#define pb push_back
#define sz size

const int mX = 1e9;
const int mxN = 1e5;
int n;

int cnt = 0;
struct node {
    int l,r,cl,cr,sum;
};

node segtree[20*mxN+1];

void upd(int idx, int t, int v){
    segtree[idx].sum += v;
    if (segtree[idx].l == segtree[idx].r){
        return;
    }
    int m = (segtree[idx].l + segtree[idx].r) / 2;
    if (m >= t){
        if (segtree[idx].cl == -1){
            segtree[cnt].l = segtree[idx].l;
            segtree[cnt].r = m;
            segtree[cnt].cl = -1;
            segtree[cnt].cr = -1;
            segtree[cnt].sum = 0;
            segtree[idx].cl = cnt;
            cnt++;
        }
        upd(segtree[idx].cl,t,v);
    }
    if (m+1 <= t){
        if (segtree[idx].cr == -1){
            segtree[cnt].l = m+1;
            segtree[cnt].r = segtree[idx].r;
            segtree[cnt].cl = -1;
            segtree[cnt].cr = -1;
            segtree[cnt].sum = 0;
            segtree[idx].cr = cnt;
            cnt++;
        }
        upd(segtree[idx].cr,t,v);
    }
}

int query(int idx, int tl, int tr){
    if (segtree[idx].l >= tl && segtree[idx].r <= tr){
        return segtree[idx].sum;
    }
    int res = 0;
    int m = (segtree[idx].l + segtree[idx].r) / 2;
    if (m >= tl && segtree[idx].cl != -1){
        res += query(segtree[idx].cl,tl,tr);
    }
    if (m+1 <= tr && segtree[idx].cr != -1){
        res += query(segtree[idx].cr,tl,tr);
    } 
    return res;
}

struct qu {
    int x,y,idx;
};

int res[mxN];
vector<pii> vals;
vector<qu> q[4*mxN+1];
vector<pii> all[4*mxN+1];

bool comp2(pii a, pii b){
    return a.f > b.f;
}

bool comp3(qu a, qu b){
    return a.x > b.x;
}

void build(int l = 0, int r = n-1, int idx = 0){
    for (int i = l; i <= r; i++) all[idx].pb(vals[i]);
    sort(all[idx].begin(),all[idx].end(),comp2);
    sort(q[idx].begin(),q[idx].end(),comp3);
    
   /* cout << l << "," << r << " " << idx << ": \n";
    for (pii curr : all[idx]){
        cout << curr.f << ',' << curr.s << " ";
    }
    cout << '\n';
    cout << q[idx].sz() << ": ";
    for (qu curr : q[idx]){
        cout << curr.x << "-" << curr.y << "-" << curr.idx << " ";
    }
    cout << '\n';
    */
    int cidx  = 0;
    for (pii curr : all[idx]){
        while (cidx < q[idx].sz() && q[idx][cidx].x > curr.f){
            res[q[idx][cidx].idx] += query(0,q[idx][cidx].y,mX);
            cidx++;
        }
      //  cout << cidx << " ";
        upd(0,curr.s,1);
    }
    while (cidx < q[idx].sz()){
        res[q[idx][cidx].idx] += query(0,q[idx][cidx].y,mX);
        cidx++;
    }
   // cout << "\n\n";
    for (pii curr : all[idx]){
        upd(0,curr.s,-1);
    }
    
    
    if (l == r) return;
    int m = (l+r)/2;
    build(l,m,2*idx+1);
    build(m+1,r,2*idx+2);
}

void add(int tl, int tr, qu v, int l =0, int r = n-1, int idx = 0){
    if (l > tr || r < tl) return;
    if (l >= tl && r <= tr){
        q[idx].pb(v);
        return;
    }
    int m = (l+r)/2;
    add(tl,tr,v,l,m,2*idx+1);
    add(tl,tr,v,m+1,r,2*idx+2);
}

bool comp(pii a, pii b){
    if (a.f + a.s == b.f + b.s) return a.f < b.f;
    return (a.f+a.s) < (b.f+b.s);
}

int main()
{
    memset(res,0,sizeof(res));
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int q;
    cin >> n >> q;
    
    vals.resize(n);
    for (int i =0; i < n; i++) cin >> vals[i].f >> vals[i].s;
    sort(vals.begin(),vals.end(),comp);
  /*  for (int i =0; i < n; i++){
        cout << vals[i].f << "," << vals[i].s << " ";
    }
    cout << '\n';*/
    segtree[cnt].l = 0;
    segtree[cnt].r = mX;
    segtree[cnt].sum = 0;
    segtree[cnt].cl = -1;
    segtree[cnt].cr = -1;
    cnt++;
    
    qu temp;
    pii t2;
    int c;
    int cidx;
    for (int i =0; i < q; i++){
        cin >> temp.x >> temp.y >> c;
        temp.idx = i;
        t2.f = -1;
        t2.s = c+1;
        cidx = lower_bound(vals.begin(),vals.end(),t2,comp) - vals.begin();
        add(cidx,n-1,temp);
    }
    
    build();
    for (int i =0; i < q; i++) cout << res[i] << "\n";
    
    return 0;
}

Compilation message

examination.cpp: In function 'void build(int, int, int)':
examination.cpp:102:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qu>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         while (cidx < q[idx].sz() && q[idx][cidx].x > curr.f){
      |                ~~~~~^~~~~~~~~~~~~
examination.cpp:109:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qu>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     while (cidx < q[idx].sz()){
      |            ~~~~~^~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 5 ms 21084 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 5 ms 21084 KB Output is correct
5 Correct 4 ms 21104 KB Output is correct
6 Correct 4 ms 21080 KB Output is correct
7 Correct 32 ms 21932 KB Output is correct
8 Correct 29 ms 21852 KB Output is correct
9 Correct 28 ms 21852 KB Output is correct
10 Correct 21 ms 21852 KB Output is correct
11 Correct 27 ms 21852 KB Output is correct
12 Correct 20 ms 21880 KB Output is correct
13 Correct 24 ms 21748 KB Output is correct
14 Correct 25 ms 21852 KB Output is correct
15 Correct 24 ms 21848 KB Output is correct
16 Correct 21 ms 21592 KB Output is correct
17 Correct 21 ms 21852 KB Output is correct
18 Correct 15 ms 21592 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 859 ms 46420 KB Output is correct
2 Correct 842 ms 46852 KB Output is correct
3 Correct 816 ms 46716 KB Output is correct
4 Correct 568 ms 44440 KB Output is correct
5 Correct 709 ms 46680 KB Output is correct
6 Correct 483 ms 44488 KB Output is correct
7 Correct 855 ms 46608 KB Output is correct
8 Correct 827 ms 46452 KB Output is correct
9 Correct 842 ms 46960 KB Output is correct
10 Correct 579 ms 46636 KB Output is correct
11 Correct 500 ms 44388 KB Output is correct
12 Correct 465 ms 44120 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 859 ms 46420 KB Output is correct
2 Correct 842 ms 46852 KB Output is correct
3 Correct 816 ms 46716 KB Output is correct
4 Correct 568 ms 44440 KB Output is correct
5 Correct 709 ms 46680 KB Output is correct
6 Correct 483 ms 44488 KB Output is correct
7 Correct 855 ms 46608 KB Output is correct
8 Correct 827 ms 46452 KB Output is correct
9 Correct 842 ms 46960 KB Output is correct
10 Correct 579 ms 46636 KB Output is correct
11 Correct 500 ms 44388 KB Output is correct
12 Correct 465 ms 44120 KB Output is correct
13 Correct 1125 ms 58792 KB Output is correct
14 Correct 1165 ms 62912 KB Output is correct
15 Correct 840 ms 49100 KB Output is correct
16 Correct 765 ms 58888 KB Output is correct
17 Correct 962 ms 60908 KB Output is correct
18 Correct 654 ms 58024 KB Output is correct
19 Correct 1118 ms 61700 KB Output is correct
20 Correct 1136 ms 62632 KB Output is correct
21 Correct 1140 ms 61944 KB Output is correct
22 Correct 583 ms 48168 KB Output is correct
23 Correct 489 ms 46072 KB Output is correct
24 Correct 463 ms 45204 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 5 ms 21084 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 5 ms 21084 KB Output is correct
5 Correct 4 ms 21104 KB Output is correct
6 Correct 4 ms 21080 KB Output is correct
7 Correct 32 ms 21932 KB Output is correct
8 Correct 29 ms 21852 KB Output is correct
9 Correct 28 ms 21852 KB Output is correct
10 Correct 21 ms 21852 KB Output is correct
11 Correct 27 ms 21852 KB Output is correct
12 Correct 20 ms 21880 KB Output is correct
13 Correct 24 ms 21748 KB Output is correct
14 Correct 25 ms 21852 KB Output is correct
15 Correct 24 ms 21848 KB Output is correct
16 Correct 21 ms 21592 KB Output is correct
17 Correct 21 ms 21852 KB Output is correct
18 Correct 15 ms 21592 KB Output is correct
19 Correct 859 ms 46420 KB Output is correct
20 Correct 842 ms 46852 KB Output is correct
21 Correct 816 ms 46716 KB Output is correct
22 Correct 568 ms 44440 KB Output is correct
23 Correct 709 ms 46680 KB Output is correct
24 Correct 483 ms 44488 KB Output is correct
25 Correct 855 ms 46608 KB Output is correct
26 Correct 827 ms 46452 KB Output is correct
27 Correct 842 ms 46960 KB Output is correct
28 Correct 579 ms 46636 KB Output is correct
29 Correct 500 ms 44388 KB Output is correct
30 Correct 465 ms 44120 KB Output is correct
31 Correct 1125 ms 58792 KB Output is correct
32 Correct 1165 ms 62912 KB Output is correct
33 Correct 840 ms 49100 KB Output is correct
34 Correct 765 ms 58888 KB Output is correct
35 Correct 962 ms 60908 KB Output is correct
36 Correct 654 ms 58024 KB Output is correct
37 Correct 1118 ms 61700 KB Output is correct
38 Correct 1136 ms 62632 KB Output is correct
39 Correct 1140 ms 61944 KB Output is correct
40 Correct 583 ms 48168 KB Output is correct
41 Correct 489 ms 46072 KB Output is correct
42 Correct 463 ms 45204 KB Output is correct
43 Correct 1524 ms 90204 KB Output is correct
44 Correct 1489 ms 90500 KB Output is correct
45 Correct 1524 ms 91664 KB Output is correct
46 Correct 755 ms 59968 KB Output is correct
47 Correct 1256 ms 88872 KB Output is correct
48 Correct 528 ms 48340 KB Output is correct
49 Correct 1536 ms 91476 KB Output is correct
50 Correct 1429 ms 90176 KB Output is correct
51 Correct 1409 ms 91300 KB Output is correct
52 Correct 1067 ms 88580 KB Output is correct
53 Correct 487 ms 46792 KB Output is correct