Submission #232011

#	Time	Username	Problem	Language	Result	Execution time	Memory
232011		Charis02	Examination (JOI19_examination)	C++14	100 / 100	1292 ms	75640 KiB

examination

#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define mid (low+high)/2
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 300004
#define INF 1e9+7

using namespace std;

struct student
{
    ll a;
    ll b;
    ll c;
    ll id;

    bool operator <(const student &s)const
    {
        return c < s.c;
    }
};

ll n,q,cnt;
student ar[N];
student queries[N];
ll seg[4*N][2];
map < ll,ll > mapper;
set < ll > values;
ll ans[N];

void update(ll low,ll high,ll pos,ll slow,ll id)
{
    if(low == slow && high==slow)
    {
        seg[pos][id]++;
        return;
    }
    if(low>slow||high<slow)
        return;

    update(low,mid,pos*2+1,slow,id);
    update(mid+1,high,pos*2+2,slow,id);

    seg[pos][id] = seg[pos*2+1][id]+seg[pos*2+2][id];
    return;
}

ll query(ll low,ll high,ll pos,ll slow,ll shigh,ll id)
{
    if(low>=slow&&high<=shigh)
        return seg[pos][id];
    if(high<slow||low>shigh)
        return 0;

    return query(low,mid,pos*2+1,slow,shigh,id)+query(mid+1,high,pos*2+2,slow,shigh,id);
}

bool by_b(const student &a,const student &b)
{
    return a.b < b.b;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;

    rep(i,0,n)
    {
        cin >> ar[i].a >> ar[i].b;
        ar[i].c = ar[i].a+ar[i].b;
        values.insert(ar[i].a);
        values.insert(ar[i].b);
    }

    sort(ar,ar+n);
    reverse(ar,ar+n);

    rep(i,0,q)
    {
        cin >> queries[i].a >> queries[i].b >> queries[i].c;
        queries[i].id=i;
        values.insert(queries[i].a);
        values.insert(queries[i].b-1);
    }

    for(set < ll >::iterator it = values.begin();it!=values.end();it++)
        mapper[(*it)]=cnt++;

    sort(queries,queries+q);
    reverse(queries,queries+q);

    ll cur = 0;

    rep(i,0,q)
    {
        if(queries[i].a + queries[i].b > queries[i].c)
            continue;

        while(cur < n && ar[cur].c >= queries[i].c)
        {
            update(0,cnt,0,mapper[ar[cur].a],0);
            update(0,cnt,0,mapper[ar[cur].b],1);
            cur++;
        }

        ll blue = query(0,cnt,0,mapper[queries[i].a],cnt,0);
        ll orange = query(0,cnt,0,0,mapper[queries[i].b-1],1);

   //     cerr << "here " << queries[i].id << " " << cur << " " << blue << " " << orange << endl;
        ans[queries[i].id] = blue-orange;
    }

    memset(seg,0,sizeof seg);
    sort(queries,queries+q,by_b);
    reverse(queries,queries+q);
    sort(ar,ar+n,by_b);
    reverse(ar,ar+n);

    cur = 0;

    rep(i,0,q)
    {
        if(queries[i].a+queries[i].b <= queries[i].c)
            continue;

        while(cur < n && ar[cur].b >= queries[i].b)
        {
            update(0,cnt,0,mapper[ar[cur].a],0);
            cur++;
        }

        ans[queries[i].id] = query(0,cnt,0,mapper[queries[i].a],cnt,0);
    }

    rep(i,0,q)
        cout << ans[i] << "\n";

    return 0;
}

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