Submission #998493

#TimeUsernameProblemLanguageResultExecution timeMemory
998493kh0iExamination (JOI19_examination)C++17
0 / 100
170 ms16428 KiB
#include "bits/stdc++.h" using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) #endif using ll = long long; using pii = pair<int, int>; #define F first #define S second #define sz(x) (int)((x).size()) #define all(x) (x).begin(), (x).end() mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll get_rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll> (l, r)(rng); } struct Fenwick{ #define gb(x) (x) & -(x) int n; vector<ll> bit; void init(int _n){ n = _n; bit.resize(n + 2, 0); } void upd(int x, ll val){ if(x == 0) return; for(; x <= n; x += gb(x)) bit[x] += val; } ll get(int l, int r){ ll res = 0; --l; for(; r; r -= gb(r)) res += bit[r]; for(; l; l -= gb(l)) res -= bit[l]; return res; } }; struct Point{ int x, y, z, id; bool operator < (const Point &o){ return x == o.x ? (y == o.y ? z >= o.z : y >= o.y) : x > o.x; } }; const int N = 2e5 + 3; int n, q, res[N]; vector<Point> p; vector<int> xx; Fenwick fen; void cdq(int l, int r){ if(l == r) return; int mid = (l + r) >> 1; cdq(l, mid); cdq(mid + 1, r); vector<Point> tmp; vector<int> ops; int a = l, b = mid + 1; while(a <= mid and b <= r){ if(p[a].y >= p[b].y){ if(p[a].id == -1){ fen.upd(p[a].z, 1); ops.push_back(p[a].z); } tmp.push_back(p[a++]); } else{ if(p[b].id >= 0) res[p[b].id] += fen.get(p[b].z, N); tmp.push_back(p[b++]); } } while(a <= mid) tmp.push_back(p[a++]); while(b <= r){ if(p[b].id >= 0) res[p[b].id] += fen.get(p[b].z, N); tmp.push_back(p[b++]); } for(int i = l; i <= r; ++i) p[i] = tmp[i - l]; for(int x : ops) fen.upd(x, -1); vector<Point>().swap(tmp); vector<int>().swap(ops); } void solve(){ cin >> n >> q; for(int i = 0; i < n; ++i){ int s, t; cin >> s >> t; p.push_back({s, t, s + t, -1}); xx.push_back(s + t); } for(int i = 0; i < q; ++i){ int a, b, c; cin >> a >> b >> c; p.push_back({a, b, c, i}); xx.push_back(c); } sort(all(xx)); xx.resize(unique(all(xx)) - xx.begin()); for(int i = 0; i < sz(p); ++i){ p[i].z = lower_bound(all(xx), p[i].z) - xx.begin() + 1; //debug(i, p[i].z); } sort(all(p)); fen.init(N); cdq(0, sz(p) - 1); for(int i = 0; i < q; ++i) cout << res[i] << '\n'; } int32_t main() { cin.tie(nullptr)->sync_with_stdio(0); #define task "troll" if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int test = 1; // cin >> test; for(int i = 1; i <= test; ++i){ // cout << "Case #" << i << ": "; solve(); } #ifdef LOCAL cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n"; #endif return 0; }

Compilation message (stderr)

examination.cpp: In function 'int32_t main()':
examination.cpp:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...