oj.uz

Submission #702573

# Submission time Handle Problem Language Result Execution time Memory
702573 2023-02-24T13:04:06 Z victor_gao Examination (JOI19_examination) C++17
0 / 100
 760 ms 89100 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);
        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=upper_bound(all[i].begin(),all[i].end(),c)-all[i].begin(); p--;
            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,2*n,1,t[i],total[i]);
        all.push_back({s[i],{t[i],total[i]}});
    }
    seg.build(1,2*n,1);
    sort(qus.begin(),qus.end());
    sort(all.begin(),all.end(),greater<pair<int,pii> >());
    int p=0;
    for (auto i:qus){
        while (p<n&&all[p].x>=i.a){
            seg.modify(1,2*n,1,all[p].y.x,all[p].y.y);
            p++;
        }
        ans[i.i]=seg.query(1,2*n,1,uni.idx(i.b),2*n,i.c);
    }
    for (int i=1;i<=q;i++)
        cout<<ans[i]<<"\n";
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 44116 KB Output is correct
2 Correct 21 ms 44184 KB Output is correct
3 Correct 24 ms 44116 KB Output is correct
4 Correct 21 ms 44088 KB Output is correct
5 Correct 21 ms 44116 KB Output is correct
6 Correct 28 ms 44116 KB Output is correct
7 Correct 33 ms 45352 KB Output is correct
8 Correct 32 ms 45268 KB Output is correct
9 Correct 33 ms 45348 KB Output is correct
10 Correct 30 ms 45404 KB Output is correct
11 Correct 33 ms 45348 KB Output is correct
12 Incorrect 28 ms 45328 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 723 ms 88136 KB Output is correct
2 Correct 736 ms 88012 KB Output is correct
3 Correct 760 ms 88036 KB Output is correct
4 Correct 478 ms 89100 KB Output is correct
5 Correct 589 ms 86152 KB Output is correct
6 Incorrect 278 ms 84032 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 723 ms 88136 KB Output is correct
2 Correct 736 ms 88012 KB Output is correct
3 Correct 760 ms 88036 KB Output is correct
4 Correct 478 ms 89100 KB Output is correct
5 Correct 589 ms 86152 KB Output is correct
6 Incorrect 278 ms 84032 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 44116 KB Output is correct
2 Correct 21 ms 44184 KB Output is correct
3 Correct 24 ms 44116 KB Output is correct
4 Correct 21 ms 44088 KB Output is correct
5 Correct 21 ms 44116 KB Output is correct
6 Correct 28 ms 44116 KB Output is correct
7 Correct 33 ms 45352 KB Output is correct
8 Correct 32 ms 45268 KB Output is correct
9 Correct 33 ms 45348 KB Output is correct
10 Correct 30 ms 45404 KB Output is correct
11 Correct 33 ms 45348 KB Output is correct
12 Incorrect 28 ms 45328 KB Output isn't correct
13 Halted 0 ms 0 KB -