Submission #1078656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078656		doducanh	Examination (JOI19_examination)	C++14	100 / 100	2192 ms	174064 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx")

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int> >, rb_tree_tag,tree_order_statistics_node_update>

#define forw(i,a,b) for(ll i=a;i<=b;i++)
#define forb(i,a,b) for(ll i=a;i>=b;i--)
#define fi first
#define se second
#define pb push_back
#define pu push
#define all(a) a.begin(),a.end()
#define getbit(mask,i) ((mask>>(i))&1)
#define minimize(a,b) (a)=min((a),(b))
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>  pll;
const ll maxN=2e5+5;
const ll mod=1e9+9;
const ll oo=1e18+1;
const int tx[4]={-1,1,0,0};
const int ty[4]={0,0,-1,1};
const int len=350;
struct fenwick
{
    vector <int> fen;
    int n;
    fenwick(int _n=1e5)
    {
        n=_n;
        fen.assign(n+5,0);
    }
    void update(int pos)
    {
        for(;pos>0;pos-=pos&-pos) fen[pos]++;
        return;
    }
    int get(int pos)
    {
        if (!pos) return 0;
        int ans=0;
        for(;pos<=n;pos+=pos&-pos) ans+=fen[pos];
        return ans;
    }
}fen[len+3];
struct dataa
{
    int x,y,z,id;
};

dataa a[maxN],query[maxN];
ordered_set save[maxN];
int n,q,ans[maxN];
vector <int> pend_x,pend_y;

bool cmp(dataa &a, dataa &b)
{
    return a.z>b.z;
}
void solve()
{
    cin>>n>>q;
    forw(i,1,n)
    {
        cin>>a[i].x>>a[i].y;
        a[i].z=a[i].x+a[i].y;
        pend_x.pb(a[i].x);
        pend_y.pb(a[i].y);
    }
    sort(a+1,a+1+n,cmp);
    sort(all(pend_x)); pend_x.resize(unique(all(pend_x))-pend_x.begin());
    sort(all(pend_y)); pend_y.resize(unique(all(pend_y))-pend_y.begin());
    forw(i,1,q)
    {
        cin>>query[i].x>>query[i].y>>query[i].z;
        query[i].id=i;
    }
    sort(query+1,query+1+q,cmp);
    int idx=1;
    forw(i,1,n)
    {
        int pos1=lower_bound(all(pend_x),a[i].x)-pend_x.begin()+1;
        int pos2=lower_bound(all(pend_y),a[i].y)-pend_y.begin()+1;
        // update ele
        save[pos1].insert({pos2,i});
        // update block
        pos1=(pos1-1)/len;
        fen[pos1].update(pos2);

        if (i<n && a[i].z==a[i+1].z) continue;

        while (idx<=q && (i==n || a[i+1].z<query[idx].z))
        {
            if (a[i].z<query[idx].z)
            {
                idx++;
                continue;
            }

            int cnt=0;
            pos1=lower_bound(all(pend_x),query[idx].x)-pend_x.begin()+1;
            pos2=lower_bound(all(pend_y),query[idx].y)-pend_y.begin()+1;
            int L=(pos1-1)/len;
            int R=(pend_x.size()-1)/len;
            // get block
            forw(block,L+1,R)
                cnt+=fen[block].get(pos2);
            // get ele
            forw(ele,pos1,(L+1)*len)
                cnt+=save[ele].size()-save[ele].order_of_key({pos2,0});

            ans[query[idx].id]=cnt;
            idx++;
        }
    }
    forw(i,1,q) cout<<ans[i]<<"\n";
    return;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    //freopen("bruh.inp","r",stdin);
    //freopen("bruh.out","w",stdout);
    int t=1; //cin>>t;
    while (t--) solve();
    return 0;
}

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