Submission #998163

#TimeUsernameProblemLanguageResultExecution timeMemory
998163cowwycowExamination (JOI19_examination)C++14
0 / 100
459 ms26956 KiB
#include <bits/stdc++.h> using namespace std; #define name "aaaaaa" using ll = long long; void file(){ ios_base::sync_with_stdio(0); cin.tie(0); if(fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } } struct node { int x, y, z, i, val; }; const int maxn = 1e6 + 5; struct BIT { int b[maxn], n; void build(int _n) { n = _n; fill(b, b + n + 1, 0); } int lowbit(int x){ return x & (-x); } void update(int x, int v){ for(int i = x; i <= n; i += lowbit(i)){ b[i] += v; } } int query(int x) { int ans = 0; for(int i = x; i > 0; i -= lowbit(i)){ ans += b[i]; } return ans; } } bit; vector<node> v; int n, q, ans[maxn]; void cdq(int l, int r) { if(l == r) return; int m = (l + r) / 2; cdq(l, m); cdq(m + 1, r); int a = l, b = m + 1, sum = 0; vector<pair<int, int>> record; vector<node> tmp; while(a <= m && b <= r){ if(v[a].y >= v[b].y){ int add = v[a].val; bit.update(v[a].z, add), sum += add, record.push_back({v[a].z, add}), tmp.push_back(v[a]); a++; }else{ ans[v[b].i] += sum - bit.query(v[b].z - 1), tmp.push_back(v[b]); b++; } } while(a <= m){ tmp.push_back(v[a]); a++; } while(b <= r){ ans[v[b].i] += sum - bit.query(v[b].z - 1), tmp.push_back(v[b]); b++; } for(int i = l; i <= r; i++){ v[i] = tmp[i - l]; } for(auto i : record) bit.update(i.first, -i.second); } bool comp(node a, node b){ return (a.x == b.x ? (a.y == b.y ? a.z < b.z : a.y < b.y) : a.x > b.x); } map<int, int> mp; void solve() { cin >> n >> q; for(int i = 0; i < n; i++){ int a, b, c; cin >> a >> b; c = a + b; mp[a] = true; mp[b] = true; mp[c] = true; v.push_back({a, b, c, i, 1}); } for(int i = n; i < n + q; i++){ int x, y, z; cin >> x >> y >> z; mp[x] = true; mp[y] = true; mp[z] = true; v.push_back({x, y, z, i, 0}); } int id = 1; for(auto i : mp){ mp[i.first] = id; id++; } for(int i = 0; i < v.size(); i++){ v[i].x = mp[v[i].x]; v[i].y = mp[v[i].y]; v[i].z = mp[v[i].z]; } bit.build(id); sort(v.begin(), v.end(), comp); cdq(0, n + q - 1); for(int i = n; i < n + q; i++) cout << ans[i] << '\n'; } int main() { file(); solve(); }

Compilation message (stderr)

examination.cpp: In function 'void solve()':
examination.cpp:109:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |  for(int i = 0; i < v.size(); i++){
      |                 ~~^~~~~~~~~~
examination.cpp: In function 'void file()':
examination.cpp:9:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |   freopen(name".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:10:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |   freopen(name".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...