oj.uz

Submission #418017

# Submission time Handle Problem Language Result Execution time Memory
418017 2021-06-04T21:17:28 Z Runtime_error_ Examination (JOI19_examination) C++14
100 / 100
 2508 ms 217860 KB 

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define ll long long
#define mid (l+r)/2
#define le node+node
#define ri node+node+1
#define pb push_back
#define mp make_pair
using namespace __gnu_pbds;
using namespace std;

typedef tree<
ll,
null_type,
less_equal<ll>,
rb_tree_tag,
tree_order_statistics_node_update>
 ordered_set;

const ll inf = 2e5+9;
ll n,q,Math[inf],Info[inf],qx[inf],qy[inf],qz[inf],qans[inf];
vector<pair<ll,ll>> events;

ll cnt;
map<ll,ll> compress;

ordered_set st[inf<<2];

void update(ll node,ll l,ll r,ll idx,ll val){
    st[node].insert(val);
    if(l == r)
        return ;
    if(idx <= mid)
        update(le,l,mid,idx,val);
    else
        update(ri,mid+1,r,idx,val);
}

ll query(ll node,ll l,ll r,ll x,ll y,ll val){
    if(l>r || r<x || l>y || x>y || st[node].empty())
        return 0;
    if(l>=x && r<=y)
        return st[node].size()- st[node].order_of_key(val);

    return query(le,l,mid,x,y,val) + query(ri,mid+1,r,x,y,val);
}

signed main(){

    scanf("%lld%lld",&n,&q);
    for(ll i=1;i<=n;i++)
        scanf("%lld%lld",Math+i,Info+i),
        events.pb( mp( Math[i]+Info[i],i ) ),compress[Math[i]] = 1;

    for(ll i=1;i<=q;i++){
        scanf("%lld%lld%lld",qx+i,qy+i,qz+i);
        compress[qx[i]] = 1;
        events.pb( mp( qz[i],-i ) );
    }

    for(auto &o:compress)
        o.second = ++cnt;
    for(ll i=1;i<=n;i++)
        Math[i] = compress[ Math[i] ];
    for(ll i=1;i<=q;i++)
        qx[i] = compress[ qx[i] ];
    sort(rall(events));
    for(auto o:events){
        ll i = o.second;
        if(i<0)//query
            i = -i,qans[i] = query(1,1,cnt,qx[i],cnt,qy[i]);
        else
            update(1,1,cnt,Math[i],Info[i]);
    }
    for(ll i=1;i<=q;i++)
        printf("%lld\n",qans[i]);
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%lld%lld",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
examination.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%lld%lld",Math+i,Info+i),
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%lld%lld%lld",qx+i,qy+i,qz+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 75460 KB Output is correct
2 Correct 63 ms 75412 KB Output is correct
3 Correct 62 ms 75428 KB Output is correct
4 Correct 62 ms 75468 KB Output is correct
5 Correct 61 ms 75372 KB Output is correct
6 Correct 76 ms 75360 KB Output is correct
7 Correct 84 ms 78624 KB Output is correct
8 Correct 81 ms 78624 KB Output is correct
9 Correct 81 ms 78672 KB Output is correct
10 Correct 80 ms 78568 KB Output is correct
11 Correct 80 ms 76612 KB Output is correct
12 Correct 81 ms 76728 KB Output is correct
13 Correct 82 ms 78708 KB Output is correct
14 Correct 82 ms 78892 KB Output is correct
15 Correct 82 ms 78664 KB Output is correct
16 Correct 94 ms 76076 KB Output is correct
17 Correct 79 ms 78644 KB Output is correct
18 Correct 79 ms 76212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2190 ms 198712 KB Output is correct
2 Correct 2224 ms 201168 KB Output is correct
3 Correct 2196 ms 201448 KB Output is correct
4 Correct 1437 ms 200476 KB Output is correct
5 Correct 509 ms 113948 KB Output is correct
6 Correct 444 ms 113304 KB Output is correct
7 Correct 2037 ms 197044 KB Output is correct
8 Correct 2009 ms 201220 KB Output is correct
9 Correct 1761 ms 197060 KB Output is correct
10 Correct 232 ms 97836 KB Output is correct
11 Correct 1244 ms 200352 KB Output is correct
12 Correct 409 ms 103176 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2190 ms 198712 KB Output is correct
2 Correct 2224 ms 201168 KB Output is correct
3 Correct 2196 ms 201448 KB Output is correct
4 Correct 1437 ms 200476 KB Output is correct
5 Correct 509 ms 113948 KB Output is correct
6 Correct 444 ms 113304 KB Output is correct
7 Correct 2037 ms 197044 KB Output is correct
8 Correct 2009 ms 201220 KB Output is correct
9 Correct 1761 ms 197060 KB Output is correct
10 Correct 232 ms 97836 KB Output is correct
11 Correct 1244 ms 200352 KB Output is correct
12 Correct 409 ms 103176 KB Output is correct
13 Correct 2138 ms 201604 KB Output is correct
14 Correct 2249 ms 201680 KB Output is correct
15 Correct 2209 ms 201208 KB Output is correct
16 Correct 1319 ms 200844 KB Output is correct
17 Correct 484 ms 114352 KB Output is correct
18 Correct 451 ms 113368 KB Output is correct
19 Correct 2005 ms 201764 KB Output is correct
20 Correct 2137 ms 201640 KB Output is correct
21 Correct 1811 ms 200424 KB Output is correct
22 Correct 236 ms 98088 KB Output is correct
23 Correct 1250 ms 200380 KB Output is correct
24 Correct 413 ms 103340 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 75460 KB Output is correct
2 Correct 63 ms 75412 KB Output is correct
3 Correct 62 ms 75428 KB Output is correct
4 Correct 62 ms 75468 KB Output is correct
5 Correct 61 ms 75372 KB Output is correct
6 Correct 76 ms 75360 KB Output is correct
7 Correct 84 ms 78624 KB Output is correct
8 Correct 81 ms 78624 KB Output is correct
9 Correct 81 ms 78672 KB Output is correct
10 Correct 80 ms 78568 KB Output is correct
11 Correct 80 ms 76612 KB Output is correct
12 Correct 81 ms 76728 KB Output is correct
13 Correct 82 ms 78708 KB Output is correct
14 Correct 82 ms 78892 KB Output is correct
15 Correct 82 ms 78664 KB Output is correct
16 Correct 94 ms 76076 KB Output is correct
17 Correct 79 ms 78644 KB Output is correct
18 Correct 79 ms 76212 KB Output is correct
19 Correct 2190 ms 198712 KB Output is correct
20 Correct 2224 ms 201168 KB Output is correct
21 Correct 2196 ms 201448 KB Output is correct
22 Correct 1437 ms 200476 KB Output is correct
23 Correct 509 ms 113948 KB Output is correct
24 Correct 444 ms 113304 KB Output is correct
25 Correct 2037 ms 197044 KB Output is correct
26 Correct 2009 ms 201220 KB Output is correct
27 Correct 1761 ms 197060 KB Output is correct
28 Correct 232 ms 97836 KB Output is correct
29 Correct 1244 ms 200352 KB Output is correct
30 Correct 409 ms 103176 KB Output is correct
31 Correct 2138 ms 201604 KB Output is correct
32 Correct 2249 ms 201680 KB Output is correct
33 Correct 2209 ms 201208 KB Output is correct
34 Correct 1319 ms 200844 KB Output is correct
35 Correct 484 ms 114352 KB Output is correct
36 Correct 451 ms 113368 KB Output is correct
37 Correct 2005 ms 201764 KB Output is correct
38 Correct 2137 ms 201640 KB Output is correct
39 Correct 1811 ms 200424 KB Output is correct
40 Correct 236 ms 98088 KB Output is correct
41 Correct 1250 ms 200380 KB Output is correct
42 Correct 413 ms 103340 KB Output is correct
43 Correct 2252 ms 217736 KB Output is correct
44 Correct 2252 ms 217640 KB Output is correct
45 Correct 2508 ms 217680 KB Output is correct
46 Correct 1501 ms 216832 KB Output is correct
47 Correct 505 ms 115624 KB Output is correct
48 Correct 411 ms 113176 KB Output is correct
49 Correct 2258 ms 217860 KB Output is correct
50 Correct 2247 ms 217716 KB Output is correct
51 Correct 2060 ms 217844 KB Output is correct
52 Correct 419 ms 99404 KB Output is correct
53 Correct 1493 ms 215796 KB Output is correct