oj.uz

Submission #102519

# Submission time Handle Problem Language Result Execution time Memory
102519 2019-03-25T15:49:40 Z Kamisama Examination (JOI19_examination) C++14
100 / 100
 2671 ms 480916 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#define taskname "JOI19_examination"
using namespace std;
const int maxn=1e5+1;
const int maxa=2e5+2;

struct Queries{
    int maths,cs,sum,id;
    inline bool operator <(const Queries &other){
        return sum>other.sum;
    }
};

struct DynamicSegTree{
    int l,r,sum;
    DynamicSegTree *cl,*cr;
    DynamicSegTree(int _l,int _r){
        l=_l; r=_r; sum=0;
        cl=nullptr; cr=nullptr;
    }
    inline void Update(const int &pos){
        if(l==r) sum++;
        else{
            int mid=(l+r)>>1;
            if(pos<=mid){
                if(cl==nullptr) cl=new DynamicSegTree(l,mid);
                cl->Update(pos);
            } else{
                if(cr==nullptr) cr=new DynamicSegTree(mid+1,r);
                cr->Update(pos);
            }
            sum=0;
            if(cl) sum+=cl->sum;
            if(cr) sum+=cr->sum;
        }
    }
    inline int Get(const int &low,const int &high){
        if(l>high || r<low) return 0;
        if(low<=l && r<=high) return sum;
        int res=0;
        if(cl) res+=cl->Get(low,high);
        if(cr) res+=cr->Get(low,high);
        return res;
    }
};

int n,q,sz;
int maths[maxa],cs[maxa],result[maxn];
Queries a[maxn],prof[maxn];
DynamicSegTree *bit[maxa];

template<typename T> inline void Read(T &x){
	register char c;
	bool neg=false;
	for(c=getchar();c<'0'||c>'9';c=getchar()) if(c=='-') neg=true;
	for(x=0;'0'<=c&&c<='9';c=getchar()) x=x*10+c-'0';
	if(neg) x=-x;
}template<typename T,typename... Args> inline void Read(T &x,Args&... args){
	Read(x);
	Read(args...);
}
template<typename T> inline void Write(T x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) Write(x/10);
	putchar(x%10+'0');
}

inline void Enter(){
    Read(n,q);
    for(int i=1;i<=n;i++){
        Read(a[i].maths,a[i].cs);
        a[i].sum=a[i].maths+a[i].cs;
        maths[i]=a[i].maths;
        cs[i]=a[i].cs;
    }
    for(int i=1;i<=q;i++){
        Read(prof[i].maths,prof[i].cs,prof[i].sum);
        prof[i].id=i;
        maths[n+i]=prof[i].maths;
        cs[n+i]=prof[i].cs;
    }
}

inline void Compress(){
    sz=n+q;
    sort(maths+1,maths+sz+1);
    sort(cs+1,cs+sz+1);
    for(int i=1;i<=n;i++){
        a[i].maths=lower_bound(maths+1,maths+sz+1,a[i].maths)-maths;
        a[i].cs=lower_bound(cs+1,cs+sz+1,a[i].cs)-cs;
    }
    for(int i=1;i<=q;i++){
        prof[i].maths=lower_bound(maths+1,maths+sz+1,prof[i].maths)-maths;
        prof[i].cs=lower_bound(cs+1,cs+sz+1,prof[i].cs)-cs;
    }
}

inline void Update(int x,const int &y){
    for(;x;x-=x&-x) bit[x]->Update(y);
}

inline int Get(int x,const int &y){
    int res=0;
    for(;x<=sz;x+=x&-x) res+=bit[x]->Get(y,sz);
    return res;
}

inline void Solve(){
    sort(a+1,a+n+1);
    sort(prof+1,prof+q+1);
    for(int i=1;i<maxa;i++) bit[i]=new DynamicSegTree(1,sz);
    for(int i=1,j=1;i<=q;i++){
        for(;j<=n && a[j].sum>=prof[i].sum;j++) Update(a[j].maths,a[j].cs);
        result[prof[i].id]=Get(prof[i].maths,prof[i].cs);
    }
    for(int i=1;i<=q;i++) Write(result[i]),putchar('\n');
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);if(fopen(taskname".INP","r"))
    freopen(taskname".INP","r",stdin),
    freopen(taskname".OUT","w",stdout);
    Enter();
    Compress();
    Solve();
    return 0;
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:124:38: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(taskname".INP","r",stdin),
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
     freopen(taskname".OUT","w",stdout);
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:124:38: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 11384 KB Output is correct
2 Correct 13 ms 11264 KB Output is correct
3 Correct 15 ms 11392 KB Output is correct
4 Correct 15 ms 11392 KB Output is correct
5 Correct 16 ms 11384 KB Output is correct
6 Correct 15 ms 11392 KB Output is correct
7 Correct 37 ms 19064 KB Output is correct
8 Correct 45 ms 19064 KB Output is correct
9 Correct 36 ms 19064 KB Output is correct
10 Correct 30 ms 16248 KB Output is correct
11 Correct 26 ms 16000 KB Output is correct
12 Correct 18 ms 11776 KB Output is correct
13 Correct 33 ms 19192 KB Output is correct
14 Correct 37 ms 19164 KB Output is correct
15 Correct 40 ms 19064 KB Output is correct
16 Correct 21 ms 11904 KB Output is correct
17 Correct 24 ms 14012 KB Output is correct
18 Correct 17 ms 11520 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2613 ms 476492 KB Output is correct
2 Correct 2545 ms 477688 KB Output is correct
3 Correct 2480 ms 477240 KB Output is correct
4 Correct 1164 ms 238864 KB Output is correct
5 Correct 871 ms 228292 KB Output is correct
6 Correct 218 ms 18296 KB Output is correct
7 Correct 2354 ms 462296 KB Output is correct
8 Correct 2135 ms 454904 KB Output is correct
9 Correct 2037 ms 439104 KB Output is correct
10 Correct 170 ms 27532 KB Output is correct
11 Correct 380 ms 108280 KB Output is correct
12 Correct 72 ms 17144 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2613 ms 476492 KB Output is correct
2 Correct 2545 ms 477688 KB Output is correct
3 Correct 2480 ms 477240 KB Output is correct
4 Correct 1164 ms 238864 KB Output is correct
5 Correct 871 ms 228292 KB Output is correct
6 Correct 218 ms 18296 KB Output is correct
7 Correct 2354 ms 462296 KB Output is correct
8 Correct 2135 ms 454904 KB Output is correct
9 Correct 2037 ms 439104 KB Output is correct
10 Correct 170 ms 27532 KB Output is correct
11 Correct 380 ms 108280 KB Output is correct
12 Correct 72 ms 17144 KB Output is correct
13 Correct 2194 ms 477936 KB Output is correct
14 Correct 2654 ms 477620 KB Output is correct
15 Correct 2669 ms 477764 KB Output is correct
16 Correct 970 ms 242020 KB Output is correct
17 Correct 878 ms 235436 KB Output is correct
18 Correct 198 ms 18336 KB Output is correct
19 Correct 2124 ms 477468 KB Output is correct
20 Correct 2205 ms 477636 KB Output is correct
21 Correct 1835 ms 464944 KB Output is correct
22 Correct 205 ms 27688 KB Output is correct
23 Correct 364 ms 108280 KB Output is correct
24 Correct 68 ms 17144 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 11384 KB Output is correct
2 Correct 13 ms 11264 KB Output is correct
3 Correct 15 ms 11392 KB Output is correct
4 Correct 15 ms 11392 KB Output is correct
5 Correct 16 ms 11384 KB Output is correct
6 Correct 15 ms 11392 KB Output is correct
7 Correct 37 ms 19064 KB Output is correct
8 Correct 45 ms 19064 KB Output is correct
9 Correct 36 ms 19064 KB Output is correct
10 Correct 30 ms 16248 KB Output is correct
11 Correct 26 ms 16000 KB Output is correct
12 Correct 18 ms 11776 KB Output is correct
13 Correct 33 ms 19192 KB Output is correct
14 Correct 37 ms 19164 KB Output is correct
15 Correct 40 ms 19064 KB Output is correct
16 Correct 21 ms 11904 KB Output is correct
17 Correct 24 ms 14012 KB Output is correct
18 Correct 17 ms 11520 KB Output is correct
19 Correct 2613 ms 476492 KB Output is correct
20 Correct 2545 ms 477688 KB Output is correct
21 Correct 2480 ms 477240 KB Output is correct
22 Correct 1164 ms 238864 KB Output is correct
23 Correct 871 ms 228292 KB Output is correct
24 Correct 218 ms 18296 KB Output is correct
25 Correct 2354 ms 462296 KB Output is correct
26 Correct 2135 ms 454904 KB Output is correct
27 Correct 2037 ms 439104 KB Output is correct
28 Correct 170 ms 27532 KB Output is correct
29 Correct 380 ms 108280 KB Output is correct
30 Correct 72 ms 17144 KB Output is correct
31 Correct 2194 ms 477936 KB Output is correct
32 Correct 2654 ms 477620 KB Output is correct
33 Correct 2669 ms 477764 KB Output is correct
34 Correct 970 ms 242020 KB Output is correct
35 Correct 878 ms 235436 KB Output is correct
36 Correct 198 ms 18336 KB Output is correct
37 Correct 2124 ms 477468 KB Output is correct
38 Correct 2205 ms 477636 KB Output is correct
39 Correct 1835 ms 464944 KB Output is correct
40 Correct 205 ms 27688 KB Output is correct
41 Correct 364 ms 108280 KB Output is correct
42 Correct 68 ms 17144 KB Output is correct
43 Correct 2181 ms 480732 KB Output is correct
44 Correct 2019 ms 480324 KB Output is correct
45 Correct 2671 ms 480916 KB Output is correct
46 Correct 903 ms 244392 KB Output is correct
47 Correct 761 ms 231520 KB Output is correct
48 Correct 170 ms 17860 KB Output is correct
49 Correct 2091 ms 467172 KB Output is correct
50 Correct 1557 ms 459384 KB Output is correct
51 Correct 1636 ms 443740 KB Output is correct
52 Correct 177 ms 30060 KB Output is correct
53 Correct 371 ms 132264 KB Output is correct