Submission #374057

#	Time	Username	Problem	Language	Result	Execution time	Memory
374057		vaaven	Examination (JOI19_examination)	C++14	100 / 100	2750 ms	97428 KiB

examination

#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <stack>
#include <iomanip>
#include <bitset>
#include <map>
#include <cassert>
#include <array>
#include <queue>
#include <cstring>
#include <random>
#include <unordered_set>
#include <unordered_map>
#define pqueue priority_queue
#define pb(x) push_back(x)
// #define endl '\n'
#define all(x) x.begin(), x.end()
 #define int long  long
      
using namespace std;
      
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
// typedef tuple<ll, ll, ll> tiii;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;
      
const int inf = 1e9 + 228;
const ll infll = 1e18;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ld eps = 1e-14;
      
      
void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    cout.tie(0);
//    freopen("d.in", "r", stdin);
//    freopen("d.out", "w", stdout);
}

struct node{
    int key, prior;
    int sz = 1;
    node *l = nullptr, *r = nullptr;
    node(int key): key(key){
        prior = rand();
    }
};

int get_sz(node *l){
    return (l ? l->sz : 0);
}

void upd(node *v){
    v->sz = 1 + get_sz(v->l) + get_sz(v->r);
}

pair<node*, node*> split(node *r, int x){
    if(!r)
        return {nullptr, nullptr};
    if(r -> key >= x){
        pair<node*, node*> mid = split(r->l, x);
        r->l = mid.second;
        upd(r);
        return {mid.first, r};
    } else{
        pair<node*, node*> mid = split(r->r, x);
        r->r = mid.first;
        upd(r);
        return {r, mid.second};
    }
}

node* merge(node *l, node *r){
    if(!l)
        return r;
    if(!r)
        return l;
    if(r->prior > l->prior){
        r->l = merge(l, r->l);
        upd(r);
        return r;
    } else{
        l->r = merge(l->r, r);
        upd(l);
        return l;
    }
}

int get(node *v, int x){
    pair<node*, node*> mid = split(v, x);
    int ans = get_sz(mid.second);
    v = merge(mid.first, mid.second);
    return ans;
}

void insert(node *&r, int x){
    node* nw = new node(x);
    pair<node*, node*> mid = split(r, x);
    r = merge(mid.first, merge(nw, mid.second));
}

const int maxn = 1e5 + 228;
node* t[maxn * 4];

void add(int v, int l, int r, int k, int k_new){
    insert(t[v], k_new);
    if(l == r)
        return;
    int mid = (l+r)/2;
    if(k <= mid)
        add(v*2, l, mid, k, k_new);
    else
        add(v*2+1, mid+1, r, k, k_new);
}

int get(int v, int l, int r, int ql, int qr, int x){
    if(ql <= l && r <= qr){
        return get(t[v], x);
    } else if(l > qr || ql > r){
        return 0;
    } else{
        int mid = (l+r)/2;
        return get(v*2, l, mid, ql, qr, x) + get(v*2+1, mid+1, r, ql, qr, x);
    }
}

struct post{
    int c, a, b, i;
    post(){}
    post(int a, int b, int c, int i): a(a), b(b), c(c), i(i){}
};

bool cmp1(pii a, pii b){
    return a.first + a.second > b.first + b.second;
}

bool cmp2(post a, post b){
    return a.c > b.c;
}

void solve(){
    int n, q;
    cin >> n >> q;
    vpii kek(n);
    vi lol;
    for(pii &i:kek){
        cin >> i.first >> i.second;
        lol.pb(i.first);
    }
    sort(all(kek), cmp1);
    vector<post> posts(q);
    for(int i=0; i<q; i++){
        int a, b, c;
        cin >> a >> b >> c;
        posts[i] = post(a, b, c, i);
    }
    sort(all(posts), cmp2);
    sort(all(lol));
    lol.resize(unique(all(lol)) - lol.begin());
    int pnt = 0;
    vi ans(q);
    for(post i:posts){
        while(pnt < n && kek[pnt].first + kek[pnt].second >= i.c){
//            cout << get_sz(t[1]) << endl;
            add(1, 0, maxn, lower_bound(all(lol), kek[pnt].first)-lol.begin(), kek[pnt].second);
//            cout << get_sz(t[1]) << endl;
            pnt++;
        }
        ans[i.i] = get(1, 0, maxn, lower_bound(all(lol), i.a)-lol.begin(), maxn, i.b);
    }
    for(int i:ans)
        cout << i << endl;
}
/*
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100
=============
10 10
41304 98327
91921 28251
85635 59191
30361 72671
28949 96958
99041 37826
10245 2726
19387 20282
60366 87723
95388 49726
52302 69501 66009
43754 45346 3158
25224 58881 18727
7298 24412 63782
24107 10583 61508
65025 29140 7278
36104 56758 2775
23126 67608 122051
56910 17272 62933
39675 15874 117117
 */

signed main(){
    fast_io();
//    srand(time(NULL));
    cout << fixed << setprecision(10);
    int q = 1;
//    cin >> q;
    while(q--)
        solve();
}

Compilation message (stderr)

examination.cpp: In constructor 'post::post(long long int, long long int, long long int, long long int)':
examination.cpp:141:15: warning: 'post::b' will be initialized after [-Wreorder]
  141 |     int c, a, b, i;
      |               ^
examination.cpp:141:9: warning:   'long long int post::c' [-Wreorder]
  141 |     int c, a, b, i;
      |         ^
examination.cpp:143:5: warning:   when initialized here [-Wreorder]
  143 |     post(int a, int b, int c, int i): a(a), b(b), c(c), i(i){}
      |     ^~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57