Submission #950887

#	Time	Username	Problem	Language	Result	Execution time	Memory
950887		idiotcomputer	Examination (JOI19_examination)	C++11	20 / 100	1143 ms	61628 KiB

examination

#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 = 2*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;
        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 (stderr)

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: 0 / 2
• Subtask 2: 20 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57