Submission #202820

#TimeUsernameProblemLanguageResultExecution timeMemory
202820RakhmandExamination (JOI19_examination)C++14
0 / 100
3114 ms689584 KiB
// // 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> ys, xs; 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, ys.size(), 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, ys.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, ys.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; xs.push_back(p[i].a); ys.push_back(p[i].b); } sort(xs.begin(), xs.end()); sort(ys.begin(), ys.end()); xs.push_back(1e9); ys.push_back(1e9); xs.erase(unique(xs.begin(), xs.end()), xs.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end()); for(int i = 1; i <= n; i++){ p[i].a = lower_bound(xs.begin(), xs.end(), p[i].a) - xs.begin(); p[i].b = lower_bound(ys.begin(), ys.end(), p[i].b) - ys.begin(); updx(rootx, 0, xs.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; for(int i = 1; i <= q; i++){ while(cnt <= n && t[i].c > p[cnt].c){ updx(rootx, 0, xs.size() - 1, p[cnt].a, p[cnt].b, -1); cnt++; } if(cnt > n) ans[t[i].ind] = 0; else{ int a = lower_bound(xs.begin(), xs.end(), t[i].a) - xs.begin(); int b = lower_bound(ys.begin(), ys.end(), t[i].b) - ys.begin(); ans[t[i].ind] = getx(rootx, 0, xs.size() - 1, a, xs.size() - 1, b, ys.size() - 1); } } for(int i = 1; i <= q; i++){ cout << ans[i] << nl; } }

Compilation message (stderr)

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);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...