oj.uz

Submission #102098

# Submission time Handle Problem Language Result Execution time Memory
102098 2019-03-22T09:34:27 Z LittleFlowers__ Examination (JOI19_examination) C++14
2 / 100
 3000 ms 187632 KB 
#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
inline void out(long long x){if(x<0) putchar('-'),x=-x;if(x>9) out(x/10);putchar(x%10+'0');}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define task "EXAMINATION"
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))

const int N=100010;
int n,q;
ii a[N];
struct id{
    int x,y,z,i;
}qry[N];

int ans[N];
vector<int> r;
map<int,map<int,int>> bit;

int upp(int i,const vector<int>&v){
    return lower_bound(all(v),i)-v.begin()+1;
}

void add(int t){
    int x,y; x=upp(a[t].fi,r), y=upp(a[t].se,r);
    for(int i=x;i;i-=i&-i)
        for(int j=y;j;j-=j&-j)
            ++bit[i][j];
}
int que(int x,int y){
    x=upp(x,r), y=upp(y,r);
    int ret=0;
    for(int i=x;i<=r.size();i+=i&-i)
        for(int j=y;j<=r.size();j+=j&-j)
            ret+=bit[i][j];
    return ret;
}

main()
{
    //freopen(task".inp","r",stdin);
    n=in,q=in;
    forinc(i,1,n) a[i]={in,in};
    sort(a+1,a+n+1,[](ii i,ii j){return i.fi+i.se>j.fi+j.se;});
    forinc(i,1,q) qry[i]={in,in,in,i};
    sort(qry+1,qry+q+1,[](id i,id j){return i.z>j.z;});

    forinc(i,1,n) r.pb(a[i].fi),r.pb(a[i].se),r.pb(a[i].fi+a[i].se);
    sort(all(r)); r.erase(unique(all(r)),r.end());

    int j=1;
    forinc(i,1,q){
        while(j<=n && a[j].fi+a[j].se>=qry[i].z){
            add(j++);
        }
        ans[qry[i].i]=que(qry[i].x,qry[i].y);
    }
    forinc(i,1,q){
        cout<<ans[i]<<"\n";
    }
}

Compilation message

examination.cpp: In function 'int que(int, int)':
examination.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=x;i<=r.size();i+=i&-i)
                 ~^~~~~~~~~~
examination.cpp:46:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=y;j<=r.size();j+=j&-j)
                     ~^~~~~~~~~~
examination.cpp: At global scope:
examination.cpp:51:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 97 ms 8952 KB Output is correct
8 Correct 89 ms 8864 KB Output is correct
9 Correct 109 ms 8932 KB Output is correct
10 Correct 39 ms 3064 KB Output is correct
11 Correct 49 ms 2680 KB Output is correct
12 Correct 6 ms 512 KB Output is correct
13 Correct 102 ms 8824 KB Output is correct
14 Correct 123 ms 8824 KB Output is correct
15 Correct 125 ms 8952 KB Output is correct
16 Correct 36 ms 1784 KB Output is correct
17 Correct 25 ms 2040 KB Output is correct
18 Correct 4 ms 640 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3021 ms 187632 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3021 ms 187632 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 97 ms 8952 KB Output is correct
8 Correct 89 ms 8864 KB Output is correct
9 Correct 109 ms 8932 KB Output is correct
10 Correct 39 ms 3064 KB Output is correct
11 Correct 49 ms 2680 KB Output is correct
12 Correct 6 ms 512 KB Output is correct
13 Correct 102 ms 8824 KB Output is correct
14 Correct 123 ms 8824 KB Output is correct
15 Correct 125 ms 8952 KB Output is correct
16 Correct 36 ms 1784 KB Output is correct
17 Correct 25 ms 2040 KB Output is correct
18 Correct 4 ms 640 KB Output is correct
19 Execution timed out 3021 ms 187632 KB Time limit exceeded
20 Halted 0 ms 0 KB -