Submission #126919

#	Time	Username	Problem	Language	Result	Execution time	Memory
126919		zoooma13	Examination (JOI19_examination)	C++14	100 / 100	2525 ms	218792 KiB

examination

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

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