Submission #1271276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271276		LmaoLmao	Examination (JOI19_examination)	C++20	2 / 100	3092 ms	20952 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 = 2e5+5;
const int INF = 1e9;
const int MOD = 998244353;  
int n,t;
int ans[N];
aa a[N],q[N];
vector<int>tree[N*4];
vector<int>nen;
vector<int> mergee(vector<int>a,vector<int>b)
{
    vector<int>c;
    merge(a.begin(),a.end(),b.begin(),b.end(),back_inserter(c));
    return c;
}
void update(int id,int l,int r,int pos,int val)
{
    if(pos>r||pos<l)return ;
    if(r==l)
    {
        tree[id].push_back(val);
        return ;
    }
    int mid=l+r>>1;
    update(id*2,l,mid,pos,val);
    update(id*2+1,mid+1,r,pos,val);
    tree[id]=mergee(tree[id*2],tree[id*2+1]);
}
int get(int id,int l,int r,int L,int R,int val)
{
    if(l>R||r<L)return 0;
    if(l>=L&&r<=R)
    {
        int j=lower_bound(tree[id].begin(),tree[id].end(),val)-tree[id].begin();
        return tree[id].size()-j;
    }
    int mid=l+r>>1;
    return get(id*2,l,mid,L,R,val)+get(id*2+1,mid+1,r,L,R,val);
}
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);
    // #ifndef ONLINE_JUDGE
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // #endif
    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]);
    }
    for(int i=1;i<=t;i++)
    {
        for(int j=0;j<3;j++)cin>>q[i][j];
        nen.push_back(q[i][2]);
        q[i][3]=i;
    }
    sort(nen.begin(),nen.end());
    nen.erase(unique(nen.begin(),nen.end()),nen.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;
    for(int i=1;i<=t;i++)q[i][2]=lower_bound(nen.begin(),nen.end(),q[i][2])-nen.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)
        {
            update(1,1,m,a[j][2],a[j][1]);
            j++;
        }
        ans[id]=get(1,1,m,z,m,y);
    }
    for(int i=1;i<=t;i++)cout<<ans[i]<<endl;
    return 0;
}
/*
██╗░░██╗██╗░░██╗░█████╗░███╗░░██╗░██████╗░              ░██████╗██╗██╗░░░██╗                ░█████╗░██╗░░░██╗████████╗███████╗
██║░██╔╝██║░░██║██╔══██╗████╗░██║██╔════╝░              ██╔════╝██║██║░░░██║                ██╔══██╗██║░░░██║╚══██╔══╝██╔════╝
█████═╝░███████║███████║██╔██╗██║██║░░██╗░              ╚█████╗░██║██║░░░██║                ██║░░╚═╝██║░░░██║░░░██║░░░█████╗░░
██╔═██╗░██╔══██║██╔══██║██║╚████║██║░░╚██╗              ░╚═══██╗██║██║░░░██║                ██║░░██╗██║░░░██║░░░██║░░░██╔══╝░░
██║░╚██╗██║░░██║██║░░██║██║░╚███║╚██████╔╝              ██████╔╝██║╚██████╔╝                ╚█████╔╝╚██████╔╝░░░██║░░░███████╗
╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚══╝░╚═════╝░              ╚═════╝░╚═╝░╚═════╝░                ░╚════╝░░╚═════╝░░░░╚═╝░░░╚══════╝
*/

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