Submission #1271282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271282		LmaoLmao	Examination (JOI19_examination)	C++20	0 / 100	47 ms	9896 KiB

examination

#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using aa = array<int,4>;

const int N = 4e5+5;
const int INF = 1e9;
const int MOD = 998244353;  

struct tri
{
    vector<array<int,2>> trie;
    vector<int> a;
    int timer=0;
    int cnt=0;
    void build() {
        trie.push_back({0,0});
        a.push_back(0);
    }
    void add(int x) {
        int u=0; 
        cnt++;
        for(int i=30;i>=0;i--) {
            while(trie.size()<=u) {
                build();
            }
            int v=(x>>i) & 1;
            if(!trie[u][v]) {
                trie[u][v]=++timer;
            }
            a[u]++;
            u=trie[u][v];
        }
        a[u]++;
    }
    int get(int x) {
        int u=0;
        int res=0;
        for(int i=30;i>=0;i--) {
            while(trie.size()<=u) {
                build();
            }
            int v=(x>>i) & 1;
            if(v) {
                if(trie[u][0]) res+=a[trie[u][0]];
            }
            if(!trie[u][v]) {
                break;
            }
            u=trie[u][v]; 
        }
        return res;
    }
};

struct SMT{ 
    tri S[N*4];
    void update(int id,int l,int r,int pos,int val) {
        if(pos<l || r<pos) return;
        S[id].add(val);
        if(l==r) return;
        int m=l+r >> 1;
        update(id*2,l,m,pos,val);
        update(id*2+1,m+1,r,pos,val);
    }
    int get(int id,int l,int r,int u,int v,int val) {
        if(v<l || r<u) return 0;
        if(u<=l && r<=v) {
            return S[id].cnt-S[id].get(val); 
        }
        int m=l+r >> 1;
        int t1=get(id*2,l,m,u,v,val);
        int t2=get(id*2+1,m+1,r,u,v,val);
        return t1+t2;
    }
} S;

int n,t;
int ans[N];
aa a[N],q[N];
vector<int>tree[N*4];
vector<int>nen;
vector<int> nen2;
bool cmp(aa a,aa b)
{
    return a[0]>b[0];
}
signed main()
{   
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);cout.tie(NULL);
    cin>>n>>t;

    for(int i=1;i<=n;i++)
    {
        cin>>a[i][0]>>a[i][1];
        a[i][2]=a[i][0]+a[i][1];
        nen.push_back(a[i][2]);
        nen2.push_back(a[i][1]);
    }
    for(int i=1;i<=t;i++)
    {
        for(int j=0;j<3;j++)cin>>q[i][j];
        nen.push_back(q[i][2]);
        nen2.push_back(q[i][1]);
        q[i][3]=i;
    }
    sort(nen.begin(),nen.end());
    nen.erase(unique(nen.begin(),nen.end()),nen.end());
    sort(nen2.begin(),nen2.end());
    nen.erase(unique(nen2.begin(),nen2.end()),nen2.end());
    int m=nen.size();
    for(int i=1;i<=n;i++) {
        a[i][2]=lower_bound(nen.begin(),nen.end(),a[i][2])-nen.begin()+1;
        a[i][1]=lower_bound(nen2.begin(),nen2.end(),a[i][1])-nen2.begin()+1;
    }
    for(int i=1;i<=t;i++){
        q[i][2]=lower_bound(nen.begin(),nen.end(),q[i][2])-nen.begin()+1;
        q[i][2]=lower_bound(nen2.begin(),nen2.end(),q[i][2])-nen2.begin()+1;
        
    }
    sort(a+1,a+n+1,cmp);
    sort(q+1,q+t+1,cmp);
    int j=1;
    for(int i=1;i<=t;i++)
    {
        int x=q[i][0],y=q[i][1],z=q[i][2],id=q[i][3];
        while(j<=n && a[j][0]>=x)
        {
            S.update(1,1,m,a[j][2],a[j][1]);
            j++;
        }
        //cout << i << endl;
        ans[id]=S.get(1,1,m,z,m,y);
    }
    for(int i=1;i<=t;i++) cout<<ans[i]<<endl;
    return 0;
}
/*
██╗░░██╗██╗░░██╗░█████╗░███╗░░██╗░██████╗░              ░██████╗██╗██╗░░░██╗                ░█████╗░██╗░░░██╗████████╗███████╗
██║░██╔╝██║░░██║██╔══██╗████╗░██║██╔════╝░              ██╔════╝██║██║░░░██║                ██╔══██╗██║░░░██║╚══██╔══╝██╔════╝
█████═╝░███████║███████║██╔██╗██║██║░░██╗░              ╚█████╗░██║██║░░░██║                ██║░░╚═╝██║░░░██║░░░██║░░░█████╗░░
██╔═██╗░██╔══██║██╔══██║██║╚████║██║░░╚██╗              ░╚═══██╗██║██║░░░██║                ██║░░██╗██║░░░██║░░░██║░░░██╔══╝░░
██║░╚██╗██║░░██║██║░░██║██║░╚███║╚██████╔╝              ██████╔╝██║╚██████╔╝                ╚█████╔╝╚██████╔╝░░░██║░░░███████╗
╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚══╝░╚═════╝░              ╚═════╝░╚═╝░╚═════╝░                ░╚════╝░░╚═════╝░░░░╚═╝░░░╚══════╝
*/

• Subtask 1: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57