Submission #779539

#	Time	Username	Problem	Language	Result	Execution time	Memory
779539		sofija6	Examination (JOI19_examination)	C++14	100 / 100	1426 ms	21380 KiB

examination

#include <bits/stdc++.h>
#define ll int
#define MAXN 100010
using namespace std;
pair<ll,ll> a[MAXN],b[MAXN];
vector<ll> sums;
unordered_map<ll,ll> comp;
ll n,q,x[MAXN],y[MAXN],z[MAXN],len,cntind[MAXN],ans[MAXN],sumab[MAXN];
bool Cmp(pair<ll,ll> p1,pair<ll,ll> p2)
{
    return p1.first>p2.first;
}
ll Find_Pos(ll x,pair<ll,ll> *p)
{
    ll l=1,r=n,mid,ans=0;
    while (l<=r)
    {
        mid=(l+r)/2;
        if (p[mid].first>=x)
        {
            ans=mid;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    return ans;
}
struct bit
{
    vector<ll> sum;
    void Init()
    {
        sum.resize(2*MAXN);
    }
    void Add(ll pos,ll val)
    {
        for (ll i=pos;i<2*MAXN;i+=i&(-i))
            sum[i]+=val;
    }
    ll Calc(ll pos)
    {
        ll ans=0;
        for (ll i=pos;i>0;i-=i&(-i))
            ans+=sum[i];
        return ans;
    }
    ll Query(ll l,ll r)
    {
        return Calc(r)-Calc(l-1);
    }
};
bit B;
struct query
{
    ll l,r,ind;
};
query qq[MAXN];
bool Cmp_Query(query q1,query q2)
{
    if (q1.l/len!=q2.l/len)
        return q1.l/len<q2.l/len;
    return q1.r<q2.r;
}
void Add(ll pos,pair<ll,ll> *p)
{
    ll i=p[pos].second;
    cntind[i]++;
    if (cntind[i]==2)
        B.Add(sumab[i],1);
}
void Remove(ll pos,pair<ll,ll> *p)
{
    ll i=p[pos].second;
    cntind[i]--;
    if (cntind[i]==1)
        B.Add(sumab[i],-1);
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    len=sqrt(n);
    for (ll i=1;i<=n;i++)
    {
        cin >> a[i].first >> b[i].first;
        a[i].second=b[i].second=i;
        sumab[i]=a[i].first+b[i].first;
        sums.push_back(sumab[i]);
    }
    sort(a+1,a+1+n,Cmp);
    sort(b+1,b+1+n,Cmp);
    for (ll i=1;i<=q;i++)
    {
        cin >> x[i] >> y[i] >> z[i];
        sums.push_back(z[i]);
    }
    sort(sums.begin(),sums.end());
    ll cnt=1;
    for (auto i : sums)
        comp[i]=cnt++;
    for (ll i=1;i<=q;i++)
    {
        qq[i].l=Find_Pos(x[i],a);
        qq[i].r=Find_Pos(y[i],b);
        qq[i].ind=i;
        z[i]=comp[z[i]];
    }
    for (ll i=1;i<=n;i++)
        sumab[i]=comp[sumab[i]];
    sort(qq+1,qq+1+q,Cmp_Query);
    ll curl=0,curr=0;
    B.Init();
    for (ll i=1;i<=q;i++)
    {
        while (curl<qq[i].l)
        {
            curl++;
            Add(curl,a);
        }
        while (curr<qq[i].r)
        {
            curr++;
            Add(curr,b);
        }
        while (curl>qq[i].l)
        {
            Remove(curl,a);
            curl--;
        }
        while (curr>qq[i].r)
        {
            Remove(curr,b);
            curr--;
        }
        ans[qq[i].ind]=B.Query(z[qq[i].ind],2*MAXN-1);
    }
    for (ll i=1;i<=q;i++)
        cout << ans[i] << "\n";
    return 0;
}

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