Submission #202856

#	Time	Username	Problem	Language	Result	Execution time	Memory
202856		Rakhmand	Examination (JOI19_examination)	C++14	100 / 100	2866 ms	333488 KiB

examination

//
//  ROIGold.cpp
//  Main calisma
//
//  Created by Rakhman on 05/02/2019.
//  Copyright © 2019 Rakhman. All rights reserved.
//

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>

#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define FOR(i, start, finish, k) for(int i = start; i <= finish; i += k)

const int MXN = 2e5 + 10;
const long long MNN = 1e6 + 200;
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
const int OO = 1e9 + 500;

typedef long long llong;
typedef unsigned long long ullong;

using namespace std;

void istxt(bool yes){
    if(yes == 1){
        freopen("balancing.in", "r", stdin);
        freopen("balancing.out", "w", stdout);
    }else{
        freopen("/Users/rakhmanabdirashov/Desktop/folder/Programming/Road2Master/Road2Master/input.txt", "r", stdin);
    }
}

int n, q, cnt = 1, ans[MXN];
vector<int> pos;

struct exam{
    int a, b, c, ind;
}p[MXN], e[MXN];

bool cmp(exam a, exam b){
    return a.c < b.c;
}

struct node{
    node *l, *r;
    int sum;
    node(){
        l = r = nullptr;
        sum = 0;
    }
};
typedef node* pnode;
pnode t[MXN];

int getsum(pnode v) { return (v == nullptr ? 0 : v -> sum); }

void updy(pnode &v, int tl, int tr, int posy, int x){
    if(v == nullptr) v = new node();
    if(tl == tr){
        v -> sum += x;
        return;
    }
    int tm = (tl + tr) / 2;
    if(posy <= tm){
        updy(v -> l, tl, tm, posy, x);
    }else{
        updy(v -> r, tm + 1, tr, posy, x);
    }
    v -> sum = getsum(v -> l) + getsum(v -> r);
}

void updx(int posx, int posy, int x){
    for( ; posx < pos.size(); posx = (posx | (posx + 1))){
        updy(t[posx], 0, pos.size() - 1, posy, x);
    }
}

int gety(pnode v, int tl, int tr, int L, int R){
    if(v == nullptr) return 0;
    if(L <= tl && tr <= R) return v -> sum;
    if(R < tl || tr < L) return 0;
    int tm = (tl + tr) / 2;
    return gety(v -> l, tl, tm, L, R) + gety(v -> r, tm + 1, tr, L, R);
}

int getx(int posx, int ly, int ry){
    int sum = 0;
    while(posx >= 0){
        sum += gety(t[posx], 0, pos.size() - 1, ly, ry);
        posx = (posx & (posx + 1)) - 1;
    }
    return sum;
}

int get(int lx, int rx, int ly, int ry){
    return getx(rx, ly, ry) - getx(lx - 1, ly, ry);
}

int main () {
    ios;
    //istxt(0);
    cin >> n >> q;
    for(int i = 0; i < MXN; i++) t[i] = new node();
    for(int i = 1; i <= n; i++){
        cin >> p[i].a >> p[i].b;
        pos.push_back(p[i].a);
        pos.push_back(p[i].b);
        p[i].c = p[i].a + p[i].b;
    }
    pos.push_back(1e9);
    sort(pos.begin(), pos.end());
    pos.erase(unique(pos.begin(), pos.end()), pos.end());
    for(int i = 1; i <= n; i++){
        p[i].a = lower_bound(pos.begin(), pos.end(), p[i].a) - pos.begin();
        p[i].b = lower_bound(pos.begin(), pos.end(), p[i].b) - pos.begin();
        updx(p[i].a, p[i].b, 1);
    }
    for(int i = 1; i <= q; i++){
        cin >> e[i].a >> e[i].b >> e[i].c;
        e[i].ind = i;
    }
    sort(e + 1, e + q + 1, cmp);
    sort(p + 1, p + n + 1, cmp);
    for(int i = 1; i <= q; i++){
        while(cnt <= n && p[cnt].c < e[i].c){
            updx(p[cnt].a, p[cnt].b, -1);
            cnt++;
        }
        if(cnt > n) ans[e[i].ind] = 0;
        else {
            int a = lower_bound(pos.begin(), pos.end(), e[i].a) - pos.begin();
            int b = lower_bound(pos.begin(), pos.end(), e[i].b) - pos.begin();
            ans[e[i].ind] = get(a, pos.size() - 1, b, pos.size() - 1);
        }
    }
    for(int i = 1; i <= q; i++){
        cout << ans[i] << nl;
    }
    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'void updx(int, int, int)':
examination.cpp:102:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for( ; posx < pos.size(); posx = (posx | (posx + 1))){
            ~~~~~^~~~~~~~~~~~
examination.cpp: In function 'void istxt(bool)':
examination.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("balancing.in", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:56:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("balancing.out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("/Users/rakhmanabdirashov/Desktop/folder/Programming/Road2Master/Road2Master/input.txt", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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