oj.uz

Submission #210375

# Submission time Handle Problem Language Result Execution time Memory
210375 2020-03-17T08:17:07 Z mhy908 Examination (JOI19_examination) C++14
20 / 100
 397 ms 18520 KB 
#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].F, -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

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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 15320 KB Output is correct
2 Correct 354 ms 17756 KB Output is correct
3 Correct 355 ms 17112 KB Output is correct
4 Correct 322 ms 17128 KB Output is correct
5 Correct 303 ms 16856 KB Output is correct
6 Correct 245 ms 15832 KB Output is correct
7 Correct 328 ms 17484 KB Output is correct
8 Correct 347 ms 17616 KB Output is correct
9 Correct 324 ms 17356 KB Output is correct
10 Correct 279 ms 16592 KB Output is correct
11 Correct 270 ms 16720 KB Output is correct
12 Correct 185 ms 14040 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 15320 KB Output is correct
2 Correct 354 ms 17756 KB Output is correct
3 Correct 355 ms 17112 KB Output is correct
4 Correct 322 ms 17128 KB Output is correct
5 Correct 303 ms 16856 KB Output is correct
6 Correct 245 ms 15832 KB Output is correct
7 Correct 328 ms 17484 KB Output is correct
8 Correct 347 ms 17616 KB Output is correct
9 Correct 324 ms 17356 KB Output is correct
10 Correct 279 ms 16592 KB Output is correct
11 Correct 270 ms 16720 KB Output is correct
12 Correct 185 ms 14040 KB Output is correct
13 Incorrect 397 ms 18520 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -