oj.uz

Submission #702572

# Submission time Handle Problem Language Result Execution time Memory
702572 2023-02-24T13:00:53 Z victor_gao Examination (JOI19_examination) C++17
0 / 100
 3000 ms 91132 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(0);
        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<=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];
long long 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 20 ms 44180 KB Output is correct
3 Correct 21 ms 44116 KB Output is correct
4 Correct 21 ms 44172 KB Output is correct
5 Correct 21 ms 44164 KB Output is correct
6 Correct 21 ms 44168 KB Output is correct
7 Correct 34 ms 45500 KB Output is correct
8 Correct 34 ms 45424 KB Output is correct
9 Correct 33 ms 45456 KB Output is correct
10 Correct 30 ms 45552 KB Output is correct
11 Correct 35 ms 45468 KB Output is correct
12 Execution timed out 3075 ms 45332 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 751 ms 90872 KB Output is correct
2 Correct 728 ms 90976 KB Output is correct
3 Correct 707 ms 90924 KB Output is correct
4 Correct 458 ms 91132 KB Output is correct
5 Correct 578 ms 88260 KB Output is correct
6 Execution timed out 3068 ms 84800 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 751 ms 90872 KB Output is correct
2 Correct 728 ms 90976 KB Output is correct
3 Correct 707 ms 90924 KB Output is correct
4 Correct 458 ms 91132 KB Output is correct
5 Correct 578 ms 88260 KB Output is correct
6 Execution timed out 3068 ms 84800 KB Time limit exceeded
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 20 ms 44180 KB Output is correct
3 Correct 21 ms 44116 KB Output is correct
4 Correct 21 ms 44172 KB Output is correct
5 Correct 21 ms 44164 KB Output is correct
6 Correct 21 ms 44168 KB Output is correct
7 Correct 34 ms 45500 KB Output is correct
8 Correct 34 ms 45424 KB Output is correct
9 Correct 33 ms 45456 KB Output is correct
10 Correct 30 ms 45552 KB Output is correct
11 Correct 35 ms 45468 KB Output is correct
12 Execution timed out 3075 ms 45332 KB Time limit exceeded
13 Halted 0 ms 0 KB -