oj.uz

Submission #418004

# Submission time Handle Problem Language Result Execution time Memory
418004 2021-06-04T20:47:09 Z Runtime_error_ Examination (JOI19_examination) C++14
0 / 100
 2201 ms 193584 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<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-1);

    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]);
}
/*
5 1
35 100
70 70
45 15
80 40
20 95
60 60 80

*/

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

# Verdict Execution time Memory Grader output
1 Correct 62 ms 75352 KB Output is correct
2 Correct 64 ms 75404 KB Output is correct
3 Correct 63 ms 75408 KB Output is correct
4 Correct 62 ms 75456 KB Output is correct
5 Correct 72 ms 75440 KB Output is correct
6 Correct 69 ms 75560 KB Output is correct
7 Correct 98 ms 78568 KB Output is correct
8 Correct 80 ms 78564 KB Output is correct
9 Correct 81 ms 78628 KB Output is correct
10 Incorrect 72 ms 77164 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 75352 KB Output is correct
2 Correct 64 ms 75404 KB Output is correct
3 Correct 63 ms 75408 KB Output is correct
4 Correct 62 ms 75456 KB Output is correct
5 Correct 72 ms 75440 KB Output is correct
6 Correct 69 ms 75560 KB Output is correct
7 Correct 98 ms 78568 KB Output is correct
8 Correct 80 ms 78564 KB Output is correct
9 Correct 81 ms 78628 KB Output is correct
10 Incorrect 72 ms 77164 KB Output isn't correct
11 Halted 0 ms 0 KB -