Submission #208193

#TimeUsernameProblemLanguageResultExecution timeMemory
208193paradoxExamination (JOI19_examination)C++17
20 / 100
390 ms19424 KiB
#include <iostream> #include <fstream> #include <vector> #include <set> #include <map> #include <cstring> #include <string> #include <cmath> #include <cassert> #include <ctime> #include <algorithm> #include <sstream> #include <list> #include <queue> #include <deque> #include <stack> #include <cstdlib> #include <cstdio> #include <iterator> #include <functional> #include <unordered_set> #include <unordered_map> using namespace std; #define fi first #define se second #define mp make_pair #define pb push_back #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define pii pair<int, int> #define vi vector<int> #define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) typedef long long ll; typedef short inth; const int N = 8e5; const int M = N + 7; const int MOD = 1e9 + 7; const ll INF = 1e16 + 17; map<int, int> px, py; struct Point { int x, y; int power; int id; int comx, comy; Point(int x, int y, int id, int new_power = -1) : x(x), y(y), power(new_power), id(id), comx(0), comy(0) { if (new_power == -1) power = x + y; }; void compress() { comx = px[x]; comy = py[y]; } }; vector<Point> p, w[2]; int n, m; inline void read() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) { int cx, cy; scanf("%d %d", &cx, &cy); p.pb(Point(cx, cy, i)); } for (int i = 1; i <= m; ++i) { int cx, cy, cs; scanf("%d %d %d", &cx, &cy, &cs); if (cx + cy >= cs) w[0].pb(Point(cx, cy, i, cs)); else w[1].pb(Point(cx, cy, i, cs)); } } inline void compress() { vector<int> ordx, ordy; for (int i = 0; i < n; ++i) { ordx.pb(p[i].x); ordy.pb(p[i].y); } for (int j = 0; j < 2; ++j) for (int i = 0; i < sz(w[j]); ++i) { ordx.pb(w[j][i].x); ordy.pb(w[j][i].y); } sort(all(ordx)); sort(all(ordy)); int timx = 0, timy = 0; for (int i = 0; i < sz(ordx); ++i) { if (!i || ordx[i] != ordx[i - 1]) px[ordx[i]] = ++timx; if (!i || ordy[i] != ordy[i - 1]) py[ordy[i]] = ++timy; } for (int i = 0; i < n; ++i) p[i].compress(); for (int i = 0; i < sz(w[0]); ++i) w[0][i].compress(); for (int i = 0; i < sz(w[1]); ++i) w[1][i].compress(); } struct Tree { int g[M]; void build() { for (int i = 0; i < M; ++i) g[i] = 0; } void upd(int pos, int val, int v = 1, int tl = 1, int tr = N) { if (tl == tr) { g[v] += val; return; } int tm = (tl + tr) >> 1; if (pos <= tm) upd(pos, val, v << 1, tl, tm); else upd(pos, val, v << 1 | 1, tm + 1, tr); g[v] = g[v << 1] + g[v << 1 | 1]; } int get(int l, int r, int v = 1, int tl = 1, int tr = N) { if (tr < l || r < tl) return 0; if (l <= tl && tr <= r) return g[v]; int tm = (tl + tr) >> 1; int f = get(l, r, v << 1, tl, tm); int s = get(l, r, v << 1 | 1, tm + 1, tr); return f + s; } } tree[2]; inline bool cmpX(const Point& a, const Point& b) { return a.x > b.x; } int ans[M]; inline void solve1() { sort(w[0].begin(), w[0].end(), cmpX); sort(all(p), cmpX); int j = 0; tree[0].build(); for (int i = 0; i < sz(w[0]); ++i) { while (j < sz(p) && p[j].x >= w[0][i].x) { tree[0].upd(p[j].comy, 1); ++j; } int res = tree[0].get(w[0][i].comy, N); ans[w[0][i].id] = res; } } inline bool cmpPower(const Point& a, const Point& b) { return a.power > b.power; } /*inline void solve2() { sort(w[1].begin(), w[1].end(), cmpPower); sort(all(p), cmpPower); int j = 0; tree[0].build(); tree[1].build(); for (int i = 0; i < sz(w[1]); ++i) { while (j < sz(p) && p[j].power >= w[1][i].power) { tree[0].upd(p[j].comx, 1); tree[1].upd(p[j].comy, 1); ++j; } int res = tree[0].get(1, w[1][i].comx - 1) + tree[1].get(1, w[1][i].comy - 1); ans[w[1][i].id] = j - res; } }*/ inline void out() { for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]); } int main() { read(); compress(); solve1(); //solve2(); out(); return 0; }

Compilation message (stderr)

examination.cpp: In function 'void read()':
examination.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &cx, &cy);
         ~~~~~^~~~~~~~~~~~~~~~~~~
examination.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &cx, &cy, &cs);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...