제출 #912642

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
912642		alexdd	Examination (JOI19_examination)	C++17	100 / 100	2880 ms	194412 KiB

examination

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

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<pair<int,int>,null_type,greater<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

int n,q,cate;
pair<int,int> a[100005];
int rez[100005];
pair<pair<int,pair<int,int>>,int> qrys[100005];
map<int,int> mp;
map<int,int> nrm;
bool cmp(pair<int,int> x, pair<int,int> y)
{
    return x.first + x.second > y.first + y.second;
}

ordered_set aint[530000];
void upd(int nod, int st, int dr, int poz, pair<int,int> newv)
{
    aint[nod].insert(newv);
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    if(poz<=mij) upd(nod*2,st,mij,poz,newv);
    else upd(nod*2+1,mij+1,dr,poz,newv);
}
int qry(int nod, int st, int dr, int le, int ri, int lim)
{
    if(le>ri)
        return 0;
    if(le==st && dr==ri)
        return aint[nod].order_of_key({lim,-1});
    int mij=(st+dr)/2;
    return qry(nod*2,st,mij,le,min(mij,ri),lim) + qry(nod*2+1,mij+1,dr,max(mij+1,le),ri,lim);
}

signed main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].first>>a[i].second;
        mp[a[i].first]++;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=q;i++)
    {
        cin>>qrys[i].first.second.first>>qrys[i].first.second.second>>qrys[i].first.first;
        qrys[i].second=i;
        mp[qrys[i].first.second.first]++;
    }
    for(auto it:mp)
        nrm[it.first]=++cate;
    sort(qrys+1,qrys+1+q);
    int poz=1;
    for(int i=q;i>0;i--)
    {
        while(poz<=n && a[poz].first+a[poz].second >= qrys[i].first.first)
        {
            ///adauga poz
            upd(1,1,cate,nrm[a[poz].first],{a[poz].second,poz});
            poz++;
        }
        rez[qrys[i].second] = qry(1,1,cate,nrm[qrys[i].first.second.first],cate,qrys[i].first.second.second);
    }
    for(int i=1;i<=q;i++)
        cout<<rez[i]<<"\n";
    return 0;
}

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