oj.uz

답안 #950887

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
950887 2024-03-20T22:12:21 Z idiotcomputer Examination (JOI19_examination) C++11
20 / 100
 1143 ms 61628 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 = 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

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 21084 KB Output is correct
2 Correct 5 ms 21084 KB Output is correct
3 Correct 5 ms 21084 KB Output is correct
4 Correct 5 ms 21084 KB Output is correct
5 Correct 5 ms 21084 KB Output is correct
6 Correct 5 ms 21084 KB Output is correct
7 Correct 28 ms 22100 KB Output is correct
8 Correct 28 ms 22108 KB Output is correct
9 Correct 29 ms 22100 KB Output is correct
10 Correct 22 ms 22188 KB Output is correct
11 Correct 28 ms 21880 KB Output is correct
12 Incorrect 20 ms 21852 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 835 ms 49332 KB Output is correct
2 Correct 854 ms 49096 KB Output is correct
3 Correct 852 ms 48936 KB Output is correct
4 Correct 586 ms 46460 KB Output is correct
5 Correct 709 ms 48416 KB Output is correct
6 Correct 498 ms 45512 KB Output is correct
7 Correct 841 ms 48828 KB Output is correct
8 Correct 848 ms 49092 KB Output is correct
9 Correct 846 ms 48764 KB Output is correct
10 Correct 596 ms 48280 KB Output is correct
11 Correct 521 ms 46236 KB Output is correct
12 Correct 479 ms 45212 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 835 ms 49332 KB Output is correct
2 Correct 854 ms 49096 KB Output is correct
3 Correct 852 ms 48936 KB Output is correct
4 Correct 586 ms 46460 KB Output is correct
5 Correct 709 ms 48416 KB Output is correct
6 Correct 498 ms 45512 KB Output is correct
7 Correct 841 ms 48828 KB Output is correct
8 Correct 848 ms 49092 KB Output is correct
9 Correct 846 ms 48764 KB Output is correct
10 Correct 596 ms 48280 KB Output is correct
11 Correct 521 ms 46236 KB Output is correct
12 Correct 479 ms 45212 KB Output is correct
13 Incorrect 1143 ms 61628 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 21084 KB Output is correct
2 Correct 5 ms 21084 KB Output is correct
3 Correct 5 ms 21084 KB Output is correct
4 Correct 5 ms 21084 KB Output is correct
5 Correct 5 ms 21084 KB Output is correct
6 Correct 5 ms 21084 KB Output is correct
7 Correct 28 ms 22100 KB Output is correct
8 Correct 28 ms 22108 KB Output is correct
9 Correct 29 ms 22100 KB Output is correct
10 Correct 22 ms 22188 KB Output is correct
11 Correct 28 ms 21880 KB Output is correct
12 Incorrect 20 ms 21852 KB Output isn't correct
13 Halted 0 ms 0 KB -