oj.uz

Submission #874920

# Submission time Handle Problem Language Result Execution time Memory
874920 2023-11-18T05:54:43 Z Requiem Examination (JOI19_examination) C++17
100 / 100
 537 ms 40236 KB 
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define all(a) a.begin(),a.end()
#define pi 3.14159265359
#define TASKNAME "examination"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef pair<ii,ii> iv;
const int MAXN = 100005;
const int block = 316;
const int MAXBLOCK = MAXN / block;
int n,q,x,start,b;
iv score[MAXN], original[MAXN];
int nxt[6*MAXN],prep[MAXN],rev[MAXN],answer[MAXN];
struct BIT{
    vector<int> roirachoa;
    vector<int> T;
    int sz=0;
    void init(int _sz){
        sz = _sz;
        T.resize(_sz+3,0);
    }
    void upd(int id,int x){
        for(int i=id;i>0;i-=i&(-i)){
            T[i] += x;
        }
    }
    int get(int id){
        int res = 0;
        for(int i=id;i<=sz;i+=i&(-i)){
            res += T[i];
        }
        return res;
    }
    int getval(int x){
        return lower_bound(all(roirachoa),x) - roirachoa.begin() + 1;
    }
};
BIT st[MAXBLOCK*4];
void push(int node,int l,int r,int pos,int x){
    st[node].roirachoa.pb(x);
    if (l==r) return;
    int mid = (l+r)>>1;
    if (pos<=mid) push(node<<1,l,mid,pos,x);
    else push(node<<1|1,mid+1,r,pos,x);
}
vector<int> listval;
vector<iv> query;

void update(int node,int l,int r,int pos,int x){
    st[node].upd(st[node].getval(x),1);
    if (l==r) return;
    int mid = (l+r)>>1;
    if (pos <= mid){
        update(node<<1,l,mid,pos,x);
    }
    else update(node<<1|1,mid+1,r,pos,x);
}
int getrange(int node,int l,int r,int u,int v,int x){
    if (l>=u and r<=v){
        return st[node].get(st[node].getval(x));
    }
    if (l>v or r<u) return 0;
    int mid = (l+r)>>1;
    return getrange(node<<1,l,mid,u,v,x) + getrange(node<<1|1,mid+1,r,u,v,x);
}
main()
{
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>score[i].se.fi>>score[i].se.se;
        score[i].fi.se = score[i].se.fi + score[i].se.se;
        listval.pb(score[i].se.fi);
        listval.pb(score[i].se.se);
        listval.pb(score[i].fi.se);
    }
    sort(score+1,score+1+n,[](const iv &a,const iv &b){
         return a.se.fi < b.se.fi;
    });

    for(int i=1;i<=q;i++){
        int x,y,z;
        cin>>x>>y>>z;
        listval.pb(x);
        listval.pb(y);
        listval.pb(z);
        query.pb({{i,x},{y,z}});
    }
    sort(listval.begin(),listval.end());
    listval.erase(unique(listval.begin(),listval.end()),listval.end());
    for(int i=1;i<=max(q,n);i++){
        if (i<=n){
            score[i].se.fi = lower_bound(all(listval),score[i].se.fi) - listval.begin() + 1;
            score[i].se.se = lower_bound(all(listval),score[i].se.se) - listval.begin() + 1;
            score[i].fi.se = lower_bound(all(listval),score[i].fi.se) - listval.begin() + 1;
        }
        if (i<=q){
            query[i-1].se.fi = lower_bound(all(listval),query[i-1].se.fi) - listval.begin() + 1;
            query[i-1].se.se = lower_bound(all(listval),query[i-1].se.se) - listval.begin() + 1;
            query[i-1].fi.se = lower_bound(all(listval),query[i-1].fi.se) - listval.begin() + 1;
        }
    }
    for(int i=1;i<=n;i++){
        score[i].fi.fi = i;
        original[i] = score[i];
    }
    int ptr = 1;
    for(int i=1;i<=listval.size();i++){
        while(ptr <= n and original[ptr].se.fi < i){
            ptr++;
        }
        if (ptr<=n) nxt[i] = original[ptr].fi.fi;
        else nxt[i] = n+1;
    }
    sort(query.begin(),query.end(),[](const iv &a,const iv &b){
         return a.se.se > b.se.se;
    });
    sort(score+1,score+1+n,[](const iv &a,const iv &b){
         return a.fi.se > b.fi.se;
    });
    for(int i=1;i<=n;i++){
        prep[i] = i / block;
        push(1,0,MAXBLOCK,prep[i],original[i].se.se);
    }
    for(int i=1;i<MAXBLOCK*4;i++){
        sort(all(st[i].roirachoa));
        st[i].roirachoa.erase(unique(all(st[i].roirachoa)),st[i].roirachoa.end());
        st[i].init(sz(st[i].roirachoa));
    }

    ptr = 1;
    for(int i=0;i<query.size();i++){
        while(ptr <= n and score[ptr].fi.se >= query[i].se.se){
            int RealIndex = score[ptr].fi.fi;
            rev[RealIndex]++;
            int b = prep[RealIndex];
            update(1,0,MAXBLOCK,b,score[ptr].se.se);
            ptr++;
        }
        start = nxt[query[i].fi.se];
        b = prep[start];
        if (start > n) continue;
        for(int j=start;j<=n;j++){
            if (original[j].se.fi >= query[i].fi.se and
                original[j].se.se >= query[i].se.fi and
                original[j].fi.se >= query[i].se.se and
                rev[j] > 0){
                    answer[query[i].fi.fi]++;
            }
            if (prep[j] != prep[j+1]) {
                break;
            }
        }
        if (b+1 <= MAXBLOCK) answer[query[i].fi.fi] += getrange(1,0,MAXBLOCK,b+1,MAXBLOCK,query[i].se.fi);

    }
    for(int i=1;i<=q;i++){
        cout<<answer[i]<<endl;
    }
}

Compilation message

examination.cpp:81:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   81 | main()
      | ^~~~
examination.cpp: In function 'int main()':
examination.cpp:127:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for(int i=1;i<=listval.size();i++){
      |                 ~^~~~~~~~~~~~~~~~
examination.cpp:151:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |     for(int i=0;i<query.size();i++){
      |                 ~^~~~~~~~~~~~~
examination.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8728 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 11 ms 9572 KB Output is correct
8 Correct 12 ms 9440 KB Output is correct
9 Correct 11 ms 9568 KB Output is correct
10 Correct 7 ms 9184 KB Output is correct
11 Correct 10 ms 9440 KB Output is correct
12 Correct 6 ms 9184 KB Output is correct
13 Correct 10 ms 9440 KB Output is correct
14 Correct 10 ms 9440 KB Output is correct
15 Correct 10 ms 9440 KB Output is correct
16 Correct 9 ms 9440 KB Output is correct
17 Correct 6 ms 9184 KB Output is correct
18 Correct 3 ms 9180 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 36232 KB Output is correct
2 Correct 439 ms 36660 KB Output is correct
3 Correct 450 ms 36404 KB Output is correct
4 Correct 216 ms 30120 KB Output is correct
5 Correct 353 ms 37172 KB Output is correct
6 Correct 176 ms 31872 KB Output is correct
7 Correct 453 ms 37264 KB Output is correct
8 Correct 394 ms 36380 KB Output is correct
9 Correct 412 ms 37344 KB Output is correct
10 Correct 306 ms 37600 KB Output is correct
11 Correct 149 ms 31164 KB Output is correct
12 Correct 80 ms 31028 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 36232 KB Output is correct
2 Correct 439 ms 36660 KB Output is correct
3 Correct 450 ms 36404 KB Output is correct
4 Correct 216 ms 30120 KB Output is correct
5 Correct 353 ms 37172 KB Output is correct
6 Correct 176 ms 31872 KB Output is correct
7 Correct 453 ms 37264 KB Output is correct
8 Correct 394 ms 36380 KB Output is correct
9 Correct 412 ms 37344 KB Output is correct
10 Correct 306 ms 37600 KB Output is correct
11 Correct 149 ms 31164 KB Output is correct
12 Correct 80 ms 31028 KB Output is correct
13 Correct 511 ms 37332 KB Output is correct
14 Correct 492 ms 36928 KB Output is correct
15 Correct 441 ms 36940 KB Output is correct
16 Correct 245 ms 31544 KB Output is correct
17 Correct 388 ms 37944 KB Output is correct
18 Correct 172 ms 30972 KB Output is correct
19 Correct 506 ms 37988 KB Output is correct
20 Correct 497 ms 36840 KB Output is correct
21 Correct 470 ms 37940 KB Output is correct
22 Correct 301 ms 36948 KB Output is correct
23 Correct 150 ms 31284 KB Output is correct
24 Correct 76 ms 29232 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8728 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 11 ms 9572 KB Output is correct
8 Correct 12 ms 9440 KB Output is correct
9 Correct 11 ms 9568 KB Output is correct
10 Correct 7 ms 9184 KB Output is correct
11 Correct 10 ms 9440 KB Output is correct
12 Correct 6 ms 9184 KB Output is correct
13 Correct 10 ms 9440 KB Output is correct
14 Correct 10 ms 9440 KB Output is correct
15 Correct 10 ms 9440 KB Output is correct
16 Correct 9 ms 9440 KB Output is correct
17 Correct 6 ms 9184 KB Output is correct
18 Correct 3 ms 9180 KB Output is correct
19 Correct 430 ms 36232 KB Output is correct
20 Correct 439 ms 36660 KB Output is correct
21 Correct 450 ms 36404 KB Output is correct
22 Correct 216 ms 30120 KB Output is correct
23 Correct 353 ms 37172 KB Output is correct
24 Correct 176 ms 31872 KB Output is correct
25 Correct 453 ms 37264 KB Output is correct
26 Correct 394 ms 36380 KB Output is correct
27 Correct 412 ms 37344 KB Output is correct
28 Correct 306 ms 37600 KB Output is correct
29 Correct 149 ms 31164 KB Output is correct
30 Correct 80 ms 31028 KB Output is correct
31 Correct 511 ms 37332 KB Output is correct
32 Correct 492 ms 36928 KB Output is correct
33 Correct 441 ms 36940 KB Output is correct
34 Correct 245 ms 31544 KB Output is correct
35 Correct 388 ms 37944 KB Output is correct
36 Correct 172 ms 30972 KB Output is correct
37 Correct 506 ms 37988 KB Output is correct
38 Correct 497 ms 36840 KB Output is correct
39 Correct 470 ms 37940 KB Output is correct
40 Correct 301 ms 36948 KB Output is correct
41 Correct 150 ms 31284 KB Output is correct
42 Correct 76 ms 29232 KB Output is correct
43 Correct 522 ms 40100 KB Output is correct
44 Correct 537 ms 38924 KB Output is correct
45 Correct 509 ms 38700 KB Output is correct
46 Correct 267 ms 33352 KB Output is correct
47 Correct 448 ms 40236 KB Output is correct
48 Correct 172 ms 31280 KB Output is correct
49 Correct 505 ms 40188 KB Output is correct
50 Correct 463 ms 39396 KB Output is correct
51 Correct 475 ms 39592 KB Output is correct
52 Correct 354 ms 38960 KB Output is correct
53 Correct 164 ms 30912 KB Output is correct