oj.uz

Submission #126919

# Submission time Handle Problem Language Result Execution time Memory
126919 2019-07-08T15:50:50 Z zoooma13 Examination (JOI19_examination) C++14
100 / 100
 2525 ms 218792 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define MAX_N 100005
#define FL (p<<1)|1
#define FR (p<<1)+2
#define all(v) (v).begin() ,(v).end()

struct cont{
    int a ,b ,c ,idx;
    bool operator<(const cont&rhs){
        return c < rhs.c;
    }
};

vector <int> comp;
int smlr(int num){
    return lower_bound(comp.begin() ,comp.end() ,num)-comp.begin();
}

int n ,q;
vector <cont> stds;
vector <cont> qs;
vector<vector <int>> pnts;

vector<ordered_set <int>> stree;
void bld(int l=0 ,int r=comp.size() ,int p=0)
{
    if(l == r){
        for(int&v : pnts[l])
            stree[p].insert(v);
        return;
    }

    int mid = (l+r)>>1;
    bld(l ,mid ,FL);
    bld(mid+1 ,r ,FR);
    for(auto&i : stree[FL])
        stree[p].insert(i);
    for(auto&i : stree[FR])
        stree[p].insert(i);
}
int qry(int ql ,int v ,int l=0 ,int r=comp.size() ,int p=0)
{
    if(ql <= l)
        return stree[p].size()-stree[p].order_of_key(v);
    if(r < ql)
        return 0;

    int mid = (l+r)>>1;
    return qry(ql ,v ,l ,mid ,FL) + qry(ql ,v ,mid+1 ,r ,FR);
}
void rem(int id ,int va ,int l=0 ,int r=comp.size() ,int p=0)
{
    stree[p].erase(stree[p].find_by_order(stree[p].order_of_key(va)));
    if(l == r)
        return;

    int mid = (l+r)>>1;
    if(id <= mid) rem(id ,va ,l ,mid ,FL);
    else          rem(id ,va ,mid+1 ,r ,FR);
}

int main()
{
    scanf("%d%d",&n,&q);
    for(int s,t,i=0; i<n; i++){
        scanf("%d%d",&s,&t);
        stds.push_back({s ,t ,s+t ,i});
        comp.push_back(s);
        comp.push_back(t);
        comp.push_back(s+t);
    }

    sort(comp.begin() ,comp.end());
    comp.resize(unique(comp.begin() ,comp.end())-comp.begin());

    pnts.resize(3*comp.size()+5);
    for(auto&s : stds){
        s.a = smlr(s.a);
        s.b = smlr(s.b);
        s.c = smlr(s.c);
        pnts[s.a].push_back(s.b);
    }

    for(int a,b,c,i=0; i<q; i++){
        scanf("%d%d%d",&a,&b,&c);
        a = smlr(a);
        b = smlr(b);
        c = smlr(c);
        qs.push_back({a ,b ,c ,i});
    }

    sort(stds.begin() ,stds.end());
    sort(qs.begin() ,qs.end());

    stree.resize(4*comp.size()+5);
    bld();

    vector <int> ans(q);
    int st_ptr = 0;
    for(cont&q : qs){
        while(st_ptr < n && stds[st_ptr].c < q.c){
            rem(stds[st_ptr].a ,stds[st_ptr].b);
            st_ptr++;
        }

        ans[q.idx] = qry(q.a ,q.b);
    }

    for(int&i : ans)
        printf("%d\n",i);
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:72: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:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&s,&t);
         ~~~~~^~~~~~~~~~~~~~
examination.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&a,&b,&c);
         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 396 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 33 ms 6136 KB Output is correct
8 Correct 38 ms 6136 KB Output is correct
9 Correct 40 ms 6064 KB Output is correct
10 Correct 26 ms 4728 KB Output is correct
11 Correct 28 ms 4692 KB Output is correct
12 Correct 12 ms 1276 KB Output is correct
13 Correct 25 ms 6136 KB Output is correct
14 Correct 27 ms 6148 KB Output is correct
15 Correct 26 ms 6136 KB Output is correct
16 Correct 19 ms 3580 KB Output is correct
17 Correct 19 ms 3580 KB Output is correct
18 Correct 6 ms 760 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1284 ms 141248 KB Output is correct
2 Correct 1277 ms 141304 KB Output is correct
3 Correct 1253 ms 141340 KB Output is correct
4 Correct 1112 ms 122384 KB Output is correct
5 Correct 1437 ms 121280 KB Output is correct
6 Correct 425 ms 32308 KB Output is correct
7 Correct 1121 ms 141180 KB Output is correct
8 Correct 1022 ms 141720 KB Output is correct
9 Correct 934 ms 141936 KB Output is correct
10 Correct 1363 ms 110732 KB Output is correct
11 Correct 942 ms 112108 KB Output is correct
12 Correct 201 ms 15992 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1284 ms 141248 KB Output is correct
2 Correct 1277 ms 141304 KB Output is correct
3 Correct 1253 ms 141340 KB Output is correct
4 Correct 1112 ms 122384 KB Output is correct
5 Correct 1437 ms 121280 KB Output is correct
6 Correct 425 ms 32308 KB Output is correct
7 Correct 1121 ms 141180 KB Output is correct
8 Correct 1022 ms 141720 KB Output is correct
9 Correct 934 ms 141936 KB Output is correct
10 Correct 1363 ms 110732 KB Output is correct
11 Correct 942 ms 112108 KB Output is correct
12 Correct 201 ms 15992 KB Output is correct
13 Correct 2403 ms 141980 KB Output is correct
14 Correct 1968 ms 143168 KB Output is correct
15 Correct 1300 ms 143120 KB Output is correct
16 Correct 1577 ms 124336 KB Output is correct
17 Correct 1935 ms 123296 KB Output is correct
18 Correct 504 ms 33260 KB Output is correct
19 Correct 2281 ms 143336 KB Output is correct
20 Correct 2317 ms 143500 KB Output is correct
21 Correct 2166 ms 143520 KB Output is correct
22 Correct 1366 ms 111856 KB Output is correct
23 Correct 1014 ms 113168 KB Output is correct
24 Correct 197 ms 16084 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 396 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 33 ms 6136 KB Output is correct
8 Correct 38 ms 6136 KB Output is correct
9 Correct 40 ms 6064 KB Output is correct
10 Correct 26 ms 4728 KB Output is correct
11 Correct 28 ms 4692 KB Output is correct
12 Correct 12 ms 1276 KB Output is correct
13 Correct 25 ms 6136 KB Output is correct
14 Correct 27 ms 6148 KB Output is correct
15 Correct 26 ms 6136 KB Output is correct
16 Correct 19 ms 3580 KB Output is correct
17 Correct 19 ms 3580 KB Output is correct
18 Correct 6 ms 760 KB Output is correct
19 Correct 1284 ms 141248 KB Output is correct
20 Correct 1277 ms 141304 KB Output is correct
21 Correct 1253 ms 141340 KB Output is correct
22 Correct 1112 ms 122384 KB Output is correct
23 Correct 1437 ms 121280 KB Output is correct
24 Correct 425 ms 32308 KB Output is correct
25 Correct 1121 ms 141180 KB Output is correct
26 Correct 1022 ms 141720 KB Output is correct
27 Correct 934 ms 141936 KB Output is correct
28 Correct 1363 ms 110732 KB Output is correct
29 Correct 942 ms 112108 KB Output is correct
30 Correct 201 ms 15992 KB Output is correct
31 Correct 2403 ms 141980 KB Output is correct
32 Correct 1968 ms 143168 KB Output is correct
33 Correct 1300 ms 143120 KB Output is correct
34 Correct 1577 ms 124336 KB Output is correct
35 Correct 1935 ms 123296 KB Output is correct
36 Correct 504 ms 33260 KB Output is correct
37 Correct 2281 ms 143336 KB Output is correct
38 Correct 2317 ms 143500 KB Output is correct
39 Correct 2166 ms 143520 KB Output is correct
40 Correct 1366 ms 111856 KB Output is correct
41 Correct 1014 ms 113168 KB Output is correct
42 Correct 197 ms 16084 KB Output is correct
43 Correct 2468 ms 217736 KB Output is correct
44 Correct 2525 ms 218592 KB Output is correct
45 Correct 2262 ms 218776 KB Output is correct
46 Correct 1684 ms 172752 KB Output is correct
47 Correct 2114 ms 170608 KB Output is correct
48 Correct 518 ms 33212 KB Output is correct
49 Correct 2009 ms 218792 KB Output is correct
50 Correct 2282 ms 218780 KB Output is correct
51 Correct 1770 ms 218716 KB Output is correct
52 Correct 1997 ms 132056 KB Output is correct
53 Correct 965 ms 132660 KB Output is correct