Submission #1271423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271423		k12_khoi	Examination (JOI19_examination)	C++17	100 / 100	461 ms	136312 KiB

examination

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second

const int N=1e5+5;

struct queries
{
    int X,Y,Z,ID;
} Q[N];

bool cmp_X(queries x,queries y)
{
    return x.X<y.X;
}

struct Node
{
    int cnt;
    int nxt[2];

    Node()
    {
        cnt=0;
        nxt[0]=nxt[1]=-1;
    }
};

vector <Node> bit[N];

int n,request,mx_bit,root,trie_spoint,save,l;
int ans[N];
pii a[N];
vector <int> ve,alter_v;

void trie_update(vector <Node> &trie,int id,int pos,int save)
{
    trie[id].cnt++;

    if (pos<0) return;

    int x=(save>>pos)&1;
    if (trie[id].nxt[x]==-1)
    {
        trie[id].nxt[x]=trie.size();
        trie.emplace_back();
    }

    trie_update(trie,trie[id].nxt[x],pos-1,save);
}

int trie_get(vector <Node> &trie,int id,int pos,int save)
{
    if (pos<0)
        return trie[id].cnt;

    int ans=0;

    int x=(save>>pos)&1;

    if (x==0 and trie[id].nxt[1]!=-1) ans+=trie[trie[id].nxt[1]].cnt;
    if (trie[id].nxt[x]!=-1) ans+=trie_get(trie,trie[id].nxt[x],pos-1,save);

    return ans;
}

void update(int u,int v)
{
    for (int idx=u;idx<=mx_bit;idx+=idx&-idx)
    trie_update(bit[idx],root,trie_spoint,v);
}

int get(int u)
{
    int ans=0;

    for (int idx=u;idx>0;idx-=idx&-idx)
    ans+=trie_get(bit[idx],root,trie_spoint,save);

    return ans;
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> request;

    ve.clear();
    alter_v.clear();
    for (int i=1;i<=n;i++)
    {
        cin >> a[i].X >> a[i].Y;
        ve.push_back(a[i].Y);
        alter_v.push_back(a[i].X+a[i].Y);
    }
    sort(a+1,a+n+1);

    sort(ve.begin(),ve.end());
    ve.resize(unique(ve.begin(),ve.end())-ve.begin());
    mx_bit=ve.size();

    sort(alter_v.begin(),alter_v.end());
    alter_v.resize(unique(alter_v.begin(),alter_v.end())-alter_v.begin());
    trie_spoint=31-__builtin_clz(alter_v.size());

    for (int i=1;i<=mx_bit;i++)
    bit[i].emplace_back();

    for (int i=1;i<=request;i++)
    {
        cin >> Q[i].X >> Q[i].Y >> Q[i].Z;
        Q[i].ID=i;
    }
    sort(Q+1,Q+request+1,cmp_X);


    root=0;
    l=n;
    for (int i=request;i>=1;i--)
    {
        while (l>0 and a[l].X>=Q[i].X)
        {
            update(mx_bit-(lower_bound(ve.begin(),ve.end(),a[l].Y)-ve.begin()),lower_bound(alter_v.begin(),alter_v.end(),a[l].X+a[l].Y)-alter_v.begin()+1);
            l--;
        }

        if (Q[i].Y<=ve.back() and Q[i].Z<=alter_v.back())
        {
            save=lower_bound(alter_v.begin(),alter_v.end(),Q[i].Z)-alter_v.begin()+1;
            ans[Q[i].ID]=get(mx_bit-(lower_bound(ve.begin(),ve.end(),Q[i].Y)-ve.begin()));
        }
        else ans[Q[i].ID]=0;
    }

    for (int i=1;i<=request;i++)
    cout << ans[i] << '\n';
}

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