oj.uz

Submission #202821

# Submission time Handle Problem Language Result Execution time Memory
202821 2020-02-18T04:59:01 Z Rakhmand Examination (JOI19_examination) C++14
2 / 100
 3000 ms 765724 KB 
//
//  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(llong i = start; i <= finish; i += k)
 
const long long MXN = 2e5 + 10;
const long long MNN = 1e6 + 200;
const long long MOD = 1e9 + 7;
const long long INF = 1e16;
const long long OO = 1e9 + 10;
 
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, ans[MXN];
vector<int> pos;

struct lol{
    int a, b, c, ind;
}p[MXN], t[MXN];

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

struct node{
    node *l, *r, *y;
    int sum = 0;
    node(){
        l = r = y = nullptr;
        sum = 0;
    }
};

typedef node* pnode;

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

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

int getx(pnode &v, int tl, int tr, int lx, int rx, int ly, int ry){
    if(v == nullptr) return 0;
    if(lx <= tl && tr <= rx){
        return gety(v -> y, 0, pos.size() - 1, ly, ry);
    }
    if(rx < tl || tr < lx){
        return 0;
    }
    int tm = (tl + tr) / 2;
    return getx(v -> l, tl, tm, lx, rx, ly, ry) + getx(v -> r, tm + 1, tr, lx, rx, ly, ry);
}

void updy(pnode &vy, pnode lv, pnode rv, int lx, int rx, int tl, int tr, int posy, int x){
    if(vy == nullptr) vy = new node();
    if(tl == tr){
        if(lx == rx){
            vy -> sum += x;
        }else{
            vy -> sum = getsum(lv) + getsum(rv);
        }
    }else{
        int tm = (tl + tr) / 2;
        if(posy <= tm){
            updy(vy -> l, (lv == nullptr ? nullptr : lv -> l), (rv == nullptr ? nullptr : rv -> l), lx, rx, tl, tm, posy, x);
        }else{
            updy(vy -> r, (lv == nullptr ? nullptr : lv -> r), (rv == nullptr ? nullptr : rv -> r), lx, rx, tm + 1, tr, posy, x);
        }
        vy -> sum = getsum(vy -> r) + getsum(vy -> l);
    }
}

void updx(pnode &v, int tl, int tr, int posx, int posy, int x){
    if(v == nullptr){
        v = new node();
    }
    if(tl == tr){
        updy(v -> y, nullptr, nullptr, tl, tr, 0, pos.size() - 1, posy, x);
        //cout << (v -> y) -> sum << nl;
        return ;
    }
    int tm = (tl + tr) / 2;
    if(posx <= tm){
        updx(v -> l, tl, tm, posx, posy, x);
    }else{
        updx(v -> r, tm + 1, tr, posx, posy, x);
    }
    updy(v -> y, (v -> l == nullptr ? nullptr : (v -> l) -> y), (v -> r == nullptr ? nullptr : (v -> r) -> y), tl, tr, 0, pos.size() - 1, posy, x);
}

pnode rootx = new node();

int main () {
    ios;
    //istxt(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> p[i].a >> p[i].b;
        p[i].ind = i;
        p[i].c = p[i].a + p[i].b;
        pos.push_back(p[i].a);
        pos.push_back(p[i].b);
    }
    sort(pos.begin(), pos.end());
    pos.push_back(1e9);
    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();
        //cout << p[i].a << ' ' << p[i].b << nl;
        updx(rootx, 0, pos.size() - 1, p[i].a, p[i].b, 1);
    }
    sort(p + 1, p + n + 1, cmp);
    for(int i = 1; i <= q; i++){
        cin >> t[i].a >> t[i].b >> t[i].c;
        t[i].ind = i;
    }
    sort(t + 1, t + q + 1, cmp);
    int cnt = 1;
    //cout << nl;
    for(int i = 1; i <= q; i++){
        while(cnt <= n && t[i].c > p[cnt].c){
            updx(rootx, 0, pos.size() - 1, p[cnt].a, p[cnt].b, -1);
            cnt++;
        }
        if(cnt > n) ans[t[i].ind] = 0;
        else{
            int a = lower_bound(pos.begin(), pos.end(), t[i].a) - pos.begin();
            int b = lower_bound(pos.begin(), pos.end(), t[i].b) - pos.begin();
            //cout << a << ' ' << b << nl;
            ans[t[i].ind] = getx(rootx, 0, pos.size() - 1, a, pos.size() - 1, b, pos.size() - 1);
        }
    }
    for(int i = 1; i <= q; i++){
        cout << ans[i] << nl;
    }
}

Compilation message

examination.cpp: In function 'void istxt(bool)':
examination.cpp:54: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:55: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:57: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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 248 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 68 ms 17144 KB Output is correct
8 Correct 73 ms 17272 KB Output is correct
9 Correct 62 ms 17380 KB Output is correct
10 Correct 28 ms 5368 KB Output is correct
11 Correct 27 ms 5112 KB Output is correct
12 Correct 9 ms 632 KB Output is correct
13 Correct 44 ms 17276 KB Output is correct
14 Correct 45 ms 17272 KB Output is correct
15 Correct 44 ms 17272 KB Output is correct
16 Correct 17 ms 4216 KB Output is correct
17 Correct 24 ms 4600 KB Output is correct
18 Correct 7 ms 632 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3111 ms 765724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3111 ms 765724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 248 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 68 ms 17144 KB Output is correct
8 Correct 73 ms 17272 KB Output is correct
9 Correct 62 ms 17380 KB Output is correct
10 Correct 28 ms 5368 KB Output is correct
11 Correct 27 ms 5112 KB Output is correct
12 Correct 9 ms 632 KB Output is correct
13 Correct 44 ms 17276 KB Output is correct
14 Correct 45 ms 17272 KB Output is correct
15 Correct 44 ms 17272 KB Output is correct
16 Correct 17 ms 4216 KB Output is correct
17 Correct 24 ms 4600 KB Output is correct
18 Correct 7 ms 632 KB Output is correct
19 Execution timed out 3111 ms 765724 KB Time limit exceeded
20 Halted 0 ms 0 KB -