oj.uz

Submission #766113

# Submission time Handle Problem Language Result Execution time Memory
766113 2023-06-25T10:23:29 Z bachhoangxuan Examination (JOI19_examination) C++17
100 / 100
 402 ms 11848 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
//#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<pii,pii>
#define mpp make_pair
#define fi first
#define se second
//const int inf=1e18;
const int mod=1e9+7;
const int maxn=100005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=500005;
const int maxl=20;
const int maxa=250000;
const int root=3;
/*
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
const int iroot=power(3,mod-2);
*/
const int base=101;

int n,q,bit[2*maxn],ans[maxn];

int sz;

vector<piii> p;

bool cmp(piii a,piii b){
    return a.fi.se<b.fi.se;
}
void update(int x,int val){
    for(int i=x;i<=sz;i+=(i&(-i))) bit[i]+=val;
}
int query(int x){
    int res=0;
    for(int i=x;i>=1;i-=(i&(-i))) res+=bit[i];
    return res;
}
void dnc(int l,int r){
    if(l>=r-1) return;
    int mid=(l+r)>>1;
    dnc(l,mid);dnc(mid,r);
    int cur=r-1;
    for(int i=mid-1;i>=l;i--){
        while(cur>=mid && p[cur].fi.se>=p[i].fi.se){
            if(p[cur].se.se==q+1) update(sz-p[cur].se.fi,1);
            cur--;
        }
        ans[p[i].se.se]+=query(sz-p[i].se.fi);
    }
    for(int i=cur+1;i<r;i++) if(p[i].se.se==q+1) update(sz-p[i].se.fi,-1);
    sort(p.begin()+l,p.begin()+r,cmp);
}
void solve(){
    cin >> n >> q;
    vector<int> com;
    for(int i=1;i<=n;i++){
        int s,t;cin >> s >> t;
        p.push_back({{s,t},{s+t,q+1}});
        com.push_back(s+t);
    }
    for(int i=1;i<=q;i++){
        int x,y,z;cin >> x >> y >> z;
        p.push_back({{x,y},{z,i}});
        com.push_back(z);
    }
    sort(com.begin(),com.end());
    com.erase(unique(com.begin(),com.end()),com.end());
    sz=(int)com.size();
    for(auto &x:p) x.se.fi=lower_bound(com.begin(),com.end(),x.se.fi)-com.begin();
    sort(p.begin(),p.end());
    dnc(0,(int)p.size());
    for(int i=1;i<=q;i++) cout << ans[i] << '\n';
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 7 ms 724 KB Output is correct
8 Correct 7 ms 748 KB Output is correct
9 Correct 7 ms 732 KB Output is correct
10 Correct 6 ms 596 KB Output is correct
11 Correct 6 ms 600 KB Output is correct
12 Correct 4 ms 596 KB Output is correct
13 Correct 7 ms 596 KB Output is correct
14 Correct 7 ms 600 KB Output is correct
15 Correct 7 ms 668 KB Output is correct
16 Correct 5 ms 596 KB Output is correct
17 Correct 5 ms 596 KB Output is correct
18 Correct 3 ms 596 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 8632 KB Output is correct
2 Correct 342 ms 9000 KB Output is correct
3 Correct 338 ms 8960 KB Output is correct
4 Correct 244 ms 8180 KB Output is correct
5 Correct 269 ms 8184 KB Output is correct
6 Correct 138 ms 7196 KB Output is correct
7 Correct 338 ms 8864 KB Output is correct
8 Correct 329 ms 8864 KB Output is correct
9 Correct 323 ms 8952 KB Output is correct
10 Correct 224 ms 8000 KB Output is correct
11 Correct 196 ms 7936 KB Output is correct
12 Correct 116 ms 6776 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 8632 KB Output is correct
2 Correct 342 ms 9000 KB Output is correct
3 Correct 338 ms 8960 KB Output is correct
4 Correct 244 ms 8180 KB Output is correct
5 Correct 269 ms 8184 KB Output is correct
6 Correct 138 ms 7196 KB Output is correct
7 Correct 338 ms 8864 KB Output is correct
8 Correct 329 ms 8864 KB Output is correct
9 Correct 323 ms 8952 KB Output is correct
10 Correct 224 ms 8000 KB Output is correct
11 Correct 196 ms 7936 KB Output is correct
12 Correct 116 ms 6776 KB Output is correct
13 Correct 363 ms 9556 KB Output is correct
14 Correct 380 ms 9500 KB Output is correct
15 Correct 345 ms 8940 KB Output is correct
16 Correct 243 ms 8636 KB Output is correct
17 Correct 292 ms 8660 KB Output is correct
18 Correct 171 ms 7164 KB Output is correct
19 Correct 370 ms 9684 KB Output is correct
20 Correct 381 ms 9572 KB Output is correct
21 Correct 402 ms 9688 KB Output is correct
22 Correct 221 ms 8048 KB Output is correct
23 Correct 199 ms 8028 KB Output is correct
24 Correct 116 ms 6776 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 7 ms 724 KB Output is correct
8 Correct 7 ms 748 KB Output is correct
9 Correct 7 ms 732 KB Output is correct
10 Correct 6 ms 596 KB Output is correct
11 Correct 6 ms 600 KB Output is correct
12 Correct 4 ms 596 KB Output is correct
13 Correct 7 ms 596 KB Output is correct
14 Correct 7 ms 600 KB Output is correct
15 Correct 7 ms 668 KB Output is correct
16 Correct 5 ms 596 KB Output is correct
17 Correct 5 ms 596 KB Output is correct
18 Correct 3 ms 596 KB Output is correct
19 Correct 344 ms 8632 KB Output is correct
20 Correct 342 ms 9000 KB Output is correct
21 Correct 338 ms 8960 KB Output is correct
22 Correct 244 ms 8180 KB Output is correct
23 Correct 269 ms 8184 KB Output is correct
24 Correct 138 ms 7196 KB Output is correct
25 Correct 338 ms 8864 KB Output is correct
26 Correct 329 ms 8864 KB Output is correct
27 Correct 323 ms 8952 KB Output is correct
28 Correct 224 ms 8000 KB Output is correct
29 Correct 196 ms 7936 KB Output is correct
30 Correct 116 ms 6776 KB Output is correct
31 Correct 363 ms 9556 KB Output is correct
32 Correct 380 ms 9500 KB Output is correct
33 Correct 345 ms 8940 KB Output is correct
34 Correct 243 ms 8636 KB Output is correct
35 Correct 292 ms 8660 KB Output is correct
36 Correct 171 ms 7164 KB Output is correct
37 Correct 370 ms 9684 KB Output is correct
38 Correct 381 ms 9572 KB Output is correct
39 Correct 402 ms 9688 KB Output is correct
40 Correct 221 ms 8048 KB Output is correct
41 Correct 199 ms 8028 KB Output is correct
42 Correct 116 ms 6776 KB Output is correct
43 Correct 397 ms 11848 KB Output is correct
44 Correct 380 ms 11844 KB Output is correct
45 Correct 378 ms 11752 KB Output is correct
46 Correct 250 ms 10252 KB Output is correct
47 Correct 313 ms 10268 KB Output is correct
48 Correct 151 ms 7028 KB Output is correct
49 Correct 394 ms 11684 KB Output is correct
50 Correct 376 ms 11764 KB Output is correct
51 Correct 355 ms 11576 KB Output is correct
52 Correct 253 ms 10128 KB Output is correct
53 Correct 196 ms 8940 KB Output is correct