Submission #418017

#	Time	Username	Problem	Language	Result	Execution time	Memory
418017		Runtime_error_	Examination (JOI19_examination)	C++14	100 / 100	2508 ms	217860 KiB

examination

#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 (stderr)

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 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57