oj.uz

Submission #786446

# Submission time Handle Problem Language Result Execution time Memory
786446 2023-07-18T07:54:58 Z winter0101 Examination (JOI19_examination) C++14
100 / 100
 2843 ms 201872 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=1e5+9;
struct cla{
long long a,b,c;
}a[maxn];
struct query{
long long x,y,z;
}b[maxn];
vector<int>node[maxn*2];
vector<int>bit[maxn*2];
int n,q,m;
void fakeupdate(int x,int y,int val){
for (;x<=m;x+=(x-(x&(x-1)))){
    for(int z=y;z<=m;z+=(z-(z&(z-1)))){
        node[x].pb(z);
    }
}
}
void fakeget(int x,int y){
for (;x>=1;x-=(x-(x&(x-1)))){
    for(int z=y;z>=1;z-=(z-(z&(z-1)))){
        node[x].pb(z);
    }
}
}
void pre(){
for1(i,1,m){
sort(all(node[i]));
vector<int>::iterator it=unique(all(node[i]));
node[i].resize(distance(node[i].begin(),it));
bit[i].resize(sz(node[i]));
}
}
void update(int x,int y,int val){
for (;x<=m;x+=(x-(x&(x-1)))){
    for(int z=y;z<=m;z+=(z-(z&(z-1)))){
        int findpos=lower_bound(node[x].begin(),node[x].end(),z)-node[x].begin();
        bit[x][findpos]+=val;
    }
}
}
int get(int x,int y){
int sum=0;
for (;x>=1;x-=(x-(x&(x-1)))){
    for(int z=y;z>=1;z-=(z-(z&(z-1)))){
        int findpos=lower_bound(node[x].begin(),node[x].end(),z)-node[x].begin();
        sum+=bit[x][findpos];
    }
}
return sum;
}
vector<int>addpoint[maxn*2];
vector<int>answer[maxn*2];
int ans[maxn];
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n>>q;
    m=n+q;
    vector<int>n1,n2,n3;
    n1.pb(1e9+1);
    n2.pb(1e9+1);
    n3.pb(2e9+1);
    for1(i,1,n){
    cin>>a[i].a>>a[i].b;
    n1.pb(a[i].a);
    n2.pb(a[i].b);
    n3.pb(a[i].a+a[i].b);
    a[i].c=a[i].a+a[i].b;
    }
    for1(i,1,q){
    cin>>b[i].x>>b[i].y>>b[i].z;
    n1.pb(b[i].x);
    n2.pb(b[i].y);
    n3.pb(b[i].z);
    }
    sort(all(n1),greater<int>());
    sort(all(n2),greater<int>());
    sort(all(n3),greater<int>());
    map<int,int>m1,m2,m3;
    for1(i,1,sz(n1)-1){
    if (n1[i]==n1[i-1])continue;
    m1[n1[i]]=m1[n1[i-1]]+1;
    }
    for1(i,1,sz(n2)-1){
    if (n2[i]==n2[i-1])continue;
    m2[n2[i]]=m2[n2[i-1]]+1;
    }
    for1(i,1,sz(n3)-1){
    if (n3[i]==n3[i-1])continue;
    m3[n3[i]]=m3[n3[i-1]]+1;
    }
    for1(i,1,n){
    a[i].a=m1[a[i].a];
    a[i].b=m2[a[i].b];
    a[i].c=m3[a[i].c];
    addpoint[a[i].a].pb(i);
    }
    for1(i,1,q){
    b[i].x=m1[b[i].x];
    b[i].y=m2[b[i].y];
    b[i].z=m3[b[i].z];
    answer[b[i].x].pb(i);
    }
    for1(i,1,m){
    for (auto v:addpoint[i]){
        fakeupdate(a[v].b,a[v].c,1);
    }
    for (auto v:answer[i]){
        fakeget(b[v].y,b[v].z);
    }
    }
    pre();
    for1(i,1,m){
    for (auto v:addpoint[i]){
        update(a[v].b,a[v].c,1);
    }
    for (auto v:answer[i]){
        ans[v]=get(b[v].y,b[v].z);
    }
    }
    /*cout<<"precal"<<'\n';
    for1(i,1,n){
    cout<<a[i].a<<" "<<a[i].b<<" "<<a[i].c<<'\n';
    }
    cout<<'\n';
    for1(i,1,q){
    cout<<b[i].x<<" "<<b[i].y<<" "<<b[i].z<<'\n';
    }*/
    for1(i,1,q)cout<<ans[i]<<'\n';

}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 9 ms 19028 KB Output is correct
3 Correct 8 ms 19028 KB Output is correct
4 Correct 8 ms 19124 KB Output is correct
5 Correct 8 ms 19028 KB Output is correct
6 Correct 8 ms 19056 KB Output is correct
7 Correct 39 ms 22492 KB Output is correct
8 Correct 35 ms 22476 KB Output is correct
9 Correct 34 ms 22484 KB Output is correct
10 Correct 31 ms 21708 KB Output is correct
11 Correct 32 ms 21964 KB Output is correct
12 Correct 23 ms 21180 KB Output is correct
13 Correct 31 ms 22464 KB Output is correct
14 Correct 31 ms 22444 KB Output is correct
15 Correct 38 ms 22356 KB Output is correct
16 Correct 27 ms 21800 KB Output is correct
17 Correct 28 ms 21844 KB Output is correct
18 Correct 20 ms 21392 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2043 ms 152044 KB Output is correct
2 Correct 1964 ms 146608 KB Output is correct
3 Correct 1934 ms 149488 KB Output is correct
4 Correct 1421 ms 120220 KB Output is correct
5 Correct 1577 ms 134080 KB Output is correct
6 Correct 1220 ms 139616 KB Output is correct
7 Correct 1955 ms 153360 KB Output is correct
8 Correct 2084 ms 146096 KB Output is correct
9 Correct 1937 ms 161436 KB Output is correct
10 Correct 1727 ms 146044 KB Output is correct
11 Correct 1333 ms 117592 KB Output is correct
12 Correct 1093 ms 142348 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2043 ms 152044 KB Output is correct
2 Correct 1964 ms 146608 KB Output is correct
3 Correct 1934 ms 149488 KB Output is correct
4 Correct 1421 ms 120220 KB Output is correct
5 Correct 1577 ms 134080 KB Output is correct
6 Correct 1220 ms 139616 KB Output is correct
7 Correct 1955 ms 153360 KB Output is correct
8 Correct 2084 ms 146096 KB Output is correct
9 Correct 1937 ms 161436 KB Output is correct
10 Correct 1727 ms 146044 KB Output is correct
11 Correct 1333 ms 117592 KB Output is correct
12 Correct 1093 ms 142348 KB Output is correct
13 Correct 2657 ms 161852 KB Output is correct
14 Correct 2757 ms 162740 KB Output is correct
15 Correct 2150 ms 152168 KB Output is correct
16 Correct 1680 ms 120360 KB Output is correct
17 Correct 2360 ms 143192 KB Output is correct
18 Correct 1134 ms 139368 KB Output is correct
19 Correct 2672 ms 161956 KB Output is correct
20 Correct 2691 ms 162308 KB Output is correct
21 Correct 2595 ms 154260 KB Output is correct
22 Correct 1542 ms 136456 KB Output is correct
23 Correct 1446 ms 117700 KB Output is correct
24 Correct 1169 ms 142388 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 9 ms 19028 KB Output is correct
3 Correct 8 ms 19028 KB Output is correct
4 Correct 8 ms 19124 KB Output is correct
5 Correct 8 ms 19028 KB Output is correct
6 Correct 8 ms 19056 KB Output is correct
7 Correct 39 ms 22492 KB Output is correct
8 Correct 35 ms 22476 KB Output is correct
9 Correct 34 ms 22484 KB Output is correct
10 Correct 31 ms 21708 KB Output is correct
11 Correct 32 ms 21964 KB Output is correct
12 Correct 23 ms 21180 KB Output is correct
13 Correct 31 ms 22464 KB Output is correct
14 Correct 31 ms 22444 KB Output is correct
15 Correct 38 ms 22356 KB Output is correct
16 Correct 27 ms 21800 KB Output is correct
17 Correct 28 ms 21844 KB Output is correct
18 Correct 20 ms 21392 KB Output is correct
19 Correct 2043 ms 152044 KB Output is correct
20 Correct 1964 ms 146608 KB Output is correct
21 Correct 1934 ms 149488 KB Output is correct
22 Correct 1421 ms 120220 KB Output is correct
23 Correct 1577 ms 134080 KB Output is correct
24 Correct 1220 ms 139616 KB Output is correct
25 Correct 1955 ms 153360 KB Output is correct
26 Correct 2084 ms 146096 KB Output is correct
27 Correct 1937 ms 161436 KB Output is correct
28 Correct 1727 ms 146044 KB Output is correct
29 Correct 1333 ms 117592 KB Output is correct
30 Correct 1093 ms 142348 KB Output is correct
31 Correct 2657 ms 161852 KB Output is correct
32 Correct 2757 ms 162740 KB Output is correct
33 Correct 2150 ms 152168 KB Output is correct
34 Correct 1680 ms 120360 KB Output is correct
35 Correct 2360 ms 143192 KB Output is correct
36 Correct 1134 ms 139368 KB Output is correct
37 Correct 2672 ms 161956 KB Output is correct
38 Correct 2691 ms 162308 KB Output is correct
39 Correct 2595 ms 154260 KB Output is correct
40 Correct 1542 ms 136456 KB Output is correct
41 Correct 1446 ms 117700 KB Output is correct
42 Correct 1169 ms 142388 KB Output is correct
43 Correct 2761 ms 194528 KB Output is correct
44 Correct 2714 ms 194468 KB Output is correct
45 Correct 2787 ms 197640 KB Output is correct
46 Correct 1752 ms 135148 KB Output is correct
47 Correct 2409 ms 169016 KB Output is correct
48 Correct 1049 ms 133384 KB Output is correct
49 Correct 2696 ms 197144 KB Output is correct
50 Correct 2843 ms 198556 KB Output is correct
51 Correct 2750 ms 201872 KB Output is correct
52 Correct 2346 ms 168112 KB Output is correct
53 Correct 1454 ms 125968 KB Output is correct