Submission #1297342

#TimeUsernameProblemLanguageResultExecution timeMemory
1297342tdkhaiExamination (JOI19_examination)C++20
2 / 100
18 ms4204 KiB
#include<bits/stdc++.h>
#define ii pair<int,int>
//#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define tdk "tdk"
#define db double

using namespace std;

const ll INF = 1e18;
const int inf=1e9;

const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};

const int N=1e5+5;
const int Q=1e5+5;
struct bit
{
    int ft[N+Q];
    void update(int u,int val)
    {
        while(u)
        {
            ft[u]+=val;
            u-=u&-u;
        }
    }
    int get(int u)
    {
        int ret=0;
        for(int i=u;i<N+Q;i+=i&-i)
        {
            ret+=ft[i];
        }
        return ret;
    }
} bit;
struct dat
{
    int a,b,c,id;
};
dat a[N];
int n,q,ans[Q];
vector<int> valx,valy;
bool cmp(dat a,dat b)
{
    if(a.c==b.c) return a.id<b.id;
    return a.c>b.c;
}
void dnc(int l,int r)
{
    if(l==r) return;
    int mid=l+r>>1;
    vector<ii> nquery;
    vector<pair<ii,int>> query;
    for(int i=l;i<=mid;i++)
    {
        if(a[i].id==0)
        {
            nquery.pb({a[i].a,a[i].b});
        }
    }
    for(int i=mid+1;i<=r;i++)
    {
        if(a[i].id)
        {
            query.pb({{a[i].a,a[i].b},a[i].id});
        }
    }
    sort(query.rbegin(),query.rend());
    sort(nquery.rbegin(),nquery.rend());
    int pt=0;
    for(int i=0;i<query.size();i++)
    {
        while(pt<nquery.size() and nquery[pt].fi>=query[i].fi.fi)
        {
            bit.update(nquery[pt].se,1);
            pt++;
        }
        ans[query[i].se]+=bit.get(query[i].fi.se);
    }
    for(int i=0;i<pt;i++)
    {
        bit.update(nquery[i].se,-1);
    }
    query.clear();
    nquery.clear();
    dnc(l,mid);
    dnc(mid+1,r);
}
void solve()
{
    cin >>n >> q;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i].a >> a[i].b;
        a[i].c=a[i].a+a[i].b;
        a[i].id=0;
        valx.pb(a[i].a);
        valy.pb(a[i].b);
    }
    for(int i=1;i<=q;i++)
    {
        cin >> a[i+n].a >> a[i+n].b >> a[i+n].c;
        a[i+n].id=i;
        valx.pb(a[i+n].a);
        valy.pb(a[i+n].b);
    }
    sort(valx.begin(),valx.end());
    sort(valy.begin(),valy.end());
    valx.erase(unique(valx.begin(),valx.end()),valx.end());
    valy.erase(unique(valy.begin(),valy.end()),valy.end());
    for(int i=1;i<=n+q;i++)
    {
        a[i].a=lower_bound(valx.begin(),valx.end(),a[i].a)-valx.begin()+1;
        a[i].b=lower_bound(valy.begin(),valy.end(),a[i].b)-valy.begin()+1;
    }
    sort(a+1,a+1+n+q,cmp);
    dnc(1,n+q);
    for(int i=1;i<=q;i++)
    {
        cout << ans[i] << '\n';
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(tdk".inp","r"))
    {
        freopen(tdk".inp","r",stdin);
        freopen(tdk".out","w",stdout);
    }
    int t=1;
//    cin >> t;
    while(t--)
    {
        solve();
        cout << '\n';
    }
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         freopen(tdk".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
examination.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         freopen(tdk".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...