Submission #210376

#	Time	Username	Problem	Language	Result	Execution time	Memory
210376		mhy908	Examination (JOI19_examination)	C++14	100 / 100	427 ms	20568 KiB

examination

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortvec(x) sort(all(x))
#define compress(x) x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=1987654321987654321;
const int inf=2000000000;
struct FENWICK{
    int tree[200010];
    int sum(int i){
        LL ans=0;
        while(i){
            ans+=tree[i];
            i-=(i&-i);
        }
        return ans;
    }
    void update(int i, int num){
        while(i<=200000){
            tree[i]+=num;
            i+=(i&-i);
        }
    }
    void cl(){memset(tree, 0, sizeof tree);}
}fen;
pair<pli, pll> query[200010];
vector<LL> idx, idy;
int ans[200010], n, q;
bool comp(pair<pli, pll> a, pair<pli, pll> b){
    if(a.F.F!=b.F.F)return a.F.F>b.F.F;
    return a.F.S<b.F.S;
}
vector<pll> upd;
vector<pair<pll, int> > que;
void DNC(int l, int r){
    if(l==r)return;
    int mid=(l+r)/2;
    DNC(l, mid); DNC(mid+1, r);
    upd.clear(); que.clear();
    for(int i=l; i<=mid; i++){
        if(!query[i].F.S)upd.pb(query[i].S);
    }
    for(int i=mid+1; i<=r; i++){
        if(query[i].F.S)que.pb(mp(query[i].S, query[i].F.S));
    }
    sort(all(upd), greater<pll>());
    sort(all(que), greater<pair<pll, int> >());
    int pv=0;
    for(auto i:que){
        for(; pv<upd.size(); pv++){
            if(upd[pv].F<i.F.F)break;
            fen.update((int)upd[pv].S, 1);
        }
        ans[i.S]+=fen.sum(200000)-fen.sum(i.F.S-1);
    }
    for(int i=0; i<pv; i++)fen.update((int)upd[i].S, -1);
}
int main(){
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld", &query[i].F.F, &query[i].S.F);
        query[i].S.S=query[i].F.F+query[i].S.F;
        idx.pb(query[i].S.F);
        idy.pb(query[i].S.S);
    }
    for(int i=n+1; i<=n+q; i++){
        scanf("%lld %lld %lld", &query[i].F.F, &query[i].S.F, &query[i].S.S);
        query[i].F.S=i-n;
        idx.pb(query[i].S.F);
        idy.pb(query[i].S.S);
    }
    sort(query+1, query+n+q+1, comp);
    sortvec(idx); sortvec(idy);
    compress(idx); compress(idy);
    for(int i=1; i<=n+q; i++){
        query[i].S.F=lower_bound(all(idx), query[i].S.F)-idx.begin()+1;
        query[i].S.S=lower_bound(all(idy), query[i].S.S)-idy.begin()+1;
    }
    DNC(1, n+q);
    for(int i=1; i<=q; i++)printf("%d\n", ans[i]);
}

Compilation message (stderr)

examination.cpp: In function 'void DNC(int, int)':
examination.cpp:59:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(; pv<upd.size(); pv++){
               ~~^~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld", &query[i].F.F, &query[i].S.F);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &query[i].F.F, &query[i].S.F, &query[i].S.S);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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