oj.uz

Submission #702576

# Submission time Handle Problem Language Result Execution time Memory
702576 2023-02-24T13:12:51 Z victor_gao Examination (JOI19_examination) C++17
100 / 100
 903 ms 93676 KB 
//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define pii pair<int,int>
#define x first
#define y second
#define N 200015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
struct lisan{
    vector<int>vt;
    void in(int x){ vt.push_back(x); }
    void build(){
        sort(vt.begin(),vt.end());
        vt.resize(unique(vt.begin(),vt.end())-vt.begin());
    }
    int idx(int x){ return upper_bound(vt.begin(),vt.end(),x)-vt.begin(); }
}uni;
struct Query{
    int a,b,c,i;
    bool operator<(const Query p)const{
        if (a!=p.a) return a>p.a;
        else if (b!=p.b) return b>p.b;
        return c>p.c;
    }
};
struct BIT{
    int n,total=0;
    vector<int>bit;
    void init(int _n){
        n=_n;
        bit.resize(n+1);
    }
    void modify(int p,int c){
        total++;
        for (;p<=n;p+=(p&-p))
            bit[p]+=c;
    }
    int query(int p){
        int ans=0;
        for (;p>0;p-=(p&-p))
            ans+=bit[p];
        return ans;
    }
};
struct segtree{
    vector<int>all[4*N];
    BIT bit[4*N];   
    void add(int l,int r,int i,int p,int c){
        all[i].push_back(c);
        if (l==r) return;
        int mid=(l+r)>>1;
        if (p<=mid) add(l,mid,2*i,p,c);
        else add(mid+1,r,2*i+1,p,c);
    }
    void build(int l,int r,int i){
        all[i].push_back(-1);
        sort(all[i].begin(),all[i].end());
        all[i].resize(unique(all[i].begin(),all[i].end())-all[i].begin());
        bit[i].init(all[i].size());
        if (l==r) return;
        int mid=(l+r)>>1;
        build(l,mid,2*i);
        build(mid+1,r,2*i+1);
    }
    void modify(int l,int r,int i,int qp,int c){
        int p=lower_bound(all[i].begin(),all[i].end(),c)-all[i].begin();
        bit[i].modify(p,1);
     //   cout<<"add "<<l<<" "<<r<<" "<<p<<'\n';
        if (l==r) return;
        int mid=(l+r)>>1;
        if (qp<=mid) modify(l,mid,2*i,qp,c);
        else modify(mid+1,r,2*i+1,qp,c);
    }
    int query(int l,int r,int i,int ll,int rr,int c){
        if (ll>rr) return 0;
        if (ll<=l&&rr>=r){
            int p=lower_bound(all[i].begin(),all[i].end(),c)-all[i].begin(); p--;
       //     cout<<"query "<<l<<" "<<r<<" "<<c<<" -> "<<p<<" "<<bit[i].total<<" "<<bit[i].query(p)<<'\n';
            return bit[i].total-bit[i].query(p);
        }
        int mid=(l+r)>>1;
        if (rr<=mid) return query(l,mid,2*i,ll,rr,c);
        else if (ll>mid) return query(mid+1,r,2*i+1,ll,rr,c);
        else return query(l,mid,2*i,ll,rr,c)+query(mid+1,r,2*i+1,ll,rr,c);
    }
}seg;
int n,q,s[N],t[N],total[N];
int ans[N];
vector<Query>qus;
vector<pair<int,pii> >all;
signed main(){
    fast
    cin>>n>>q;
    for (int i=1;i<=n;i++){
        cin>>s[i]>>t[i];
        uni.in(t[i]);
        total[i]=s[i]+t[i];
    }
    for (int i=1;i<=q;i++){
        Query p; p.i=i;
        cin>>p.a>>p.b>>p.c;
        uni.in(p.b);
        qus.push_back(p);
    }
    uni.build();
    for (int i=1;i<=n;i++){
        t[i]=uni.idx(t[i]);
        seg.add(1,n+q,1,t[i],total[i]);
        all.push_back({s[i],{t[i],total[i]}});
    }
    seg.build(1,n+q,1);
    sort(qus.begin(),qus.end());
    sort(all.begin(),all.end(),greater<pair<int,pii> >());
    /*
    cout<<'\n';
    for (auto i:all){
        cout<<i.x<<' '<<i.y.x<<" "<<i.y.y<<'\n';
    }
    cout<<'\n';
    */
    int p=0;
    for (auto i:qus){
        while (p<n&&all[p].x>=i.a){
            seg.modify(1,n+q,1,all[p].y.x,all[p].y.y);
            p++;
        }
        ans[i.i]=seg.query(1,n+q,1,uni.idx(i.b),n+q,i.c);
       // cout<<i.a<<" "<<uni.idx(i.b)<<" "<<i.c<<" -> "<<p<<" is "<<ans[i.i]<<'\n';
    }
    for (int i=1;i<=q;i++)
        cout<<ans[i]<<"\n";
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 44116 KB Output is correct
2 Correct 20 ms 44184 KB Output is correct
3 Correct 21 ms 44180 KB Output is correct
4 Correct 22 ms 44104 KB Output is correct
5 Correct 21 ms 44136 KB Output is correct
6 Correct 21 ms 44188 KB Output is correct
7 Correct 33 ms 45260 KB Output is correct
8 Correct 32 ms 45268 KB Output is correct
9 Correct 32 ms 45344 KB Output is correct
10 Correct 31 ms 45508 KB Output is correct
11 Correct 37 ms 45244 KB Output is correct
12 Correct 28 ms 45364 KB Output is correct
13 Correct 34 ms 45396 KB Output is correct
14 Correct 35 ms 45380 KB Output is correct
15 Correct 32 ms 45424 KB Output is correct
16 Correct 32 ms 45328 KB Output is correct
17 Correct 31 ms 45556 KB Output is correct
18 Correct 27 ms 45312 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 746 ms 88036 KB Output is correct
2 Correct 718 ms 88140 KB Output is correct
3 Correct 737 ms 88036 KB Output is correct
4 Correct 454 ms 89040 KB Output is correct
5 Correct 616 ms 86160 KB Output is correct
6 Correct 292 ms 84024 KB Output is correct
7 Correct 846 ms 90512 KB Output is correct
8 Correct 675 ms 91856 KB Output is correct
9 Correct 711 ms 91832 KB Output is correct
10 Correct 531 ms 87560 KB Output is correct
11 Correct 428 ms 89732 KB Output is correct
12 Correct 227 ms 83944 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 746 ms 88036 KB Output is correct
2 Correct 718 ms 88140 KB Output is correct
3 Correct 737 ms 88036 KB Output is correct
4 Correct 454 ms 89040 KB Output is correct
5 Correct 616 ms 86160 KB Output is correct
6 Correct 292 ms 84024 KB Output is correct
7 Correct 846 ms 90512 KB Output is correct
8 Correct 675 ms 91856 KB Output is correct
9 Correct 711 ms 91832 KB Output is correct
10 Correct 531 ms 87560 KB Output is correct
11 Correct 428 ms 89732 KB Output is correct
12 Correct 227 ms 83944 KB Output is correct
13 Correct 872 ms 90380 KB Output is correct
14 Correct 791 ms 90340 KB Output is correct
15 Correct 739 ms 90356 KB Output is correct
16 Correct 493 ms 91136 KB Output is correct
17 Correct 625 ms 88344 KB Output is correct
18 Correct 286 ms 85176 KB Output is correct
19 Correct 798 ms 90280 KB Output is correct
20 Correct 828 ms 90372 KB Output is correct
21 Correct 787 ms 91200 KB Output is correct
22 Correct 518 ms 87496 KB Output is correct
23 Correct 427 ms 89664 KB Output is correct
24 Correct 238 ms 83972 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 44116 KB Output is correct
2 Correct 20 ms 44184 KB Output is correct
3 Correct 21 ms 44180 KB Output is correct
4 Correct 22 ms 44104 KB Output is correct
5 Correct 21 ms 44136 KB Output is correct
6 Correct 21 ms 44188 KB Output is correct
7 Correct 33 ms 45260 KB Output is correct
8 Correct 32 ms 45268 KB Output is correct
9 Correct 32 ms 45344 KB Output is correct
10 Correct 31 ms 45508 KB Output is correct
11 Correct 37 ms 45244 KB Output is correct
12 Correct 28 ms 45364 KB Output is correct
13 Correct 34 ms 45396 KB Output is correct
14 Correct 35 ms 45380 KB Output is correct
15 Correct 32 ms 45424 KB Output is correct
16 Correct 32 ms 45328 KB Output is correct
17 Correct 31 ms 45556 KB Output is correct
18 Correct 27 ms 45312 KB Output is correct
19 Correct 746 ms 88036 KB Output is correct
20 Correct 718 ms 88140 KB Output is correct
21 Correct 737 ms 88036 KB Output is correct
22 Correct 454 ms 89040 KB Output is correct
23 Correct 616 ms 86160 KB Output is correct
24 Correct 292 ms 84024 KB Output is correct
25 Correct 846 ms 90512 KB Output is correct
26 Correct 675 ms 91856 KB Output is correct
27 Correct 711 ms 91832 KB Output is correct
28 Correct 531 ms 87560 KB Output is correct
29 Correct 428 ms 89732 KB Output is correct
30 Correct 227 ms 83944 KB Output is correct
31 Correct 872 ms 90380 KB Output is correct
32 Correct 791 ms 90340 KB Output is correct
33 Correct 739 ms 90356 KB Output is correct
34 Correct 493 ms 91136 KB Output is correct
35 Correct 625 ms 88344 KB Output is correct
36 Correct 286 ms 85176 KB Output is correct
37 Correct 798 ms 90280 KB Output is correct
38 Correct 828 ms 90372 KB Output is correct
39 Correct 787 ms 91200 KB Output is correct
40 Correct 518 ms 87496 KB Output is correct
41 Correct 427 ms 89664 KB Output is correct
42 Correct 238 ms 83972 KB Output is correct
43 Correct 844 ms 89932 KB Output is correct
44 Correct 903 ms 90008 KB Output is correct
45 Correct 794 ms 90024 KB Output is correct
46 Correct 514 ms 93676 KB Output is correct
47 Correct 651 ms 89920 KB Output is correct
48 Correct 281 ms 84892 KB Output is correct
49 Correct 796 ms 90028 KB Output is correct
50 Correct 800 ms 90300 KB Output is correct
51 Correct 772 ms 90240 KB Output is correct
52 Correct 583 ms 89868 KB Output is correct
53 Correct 422 ms 93004 KB Output is correct