Submission #1020252

#TimeUsernameProblemLanguageResultExecution timeMemory
1020252codefoxExamination (JOI19_examination)C++14
0 / 100
1806 ms470400 KiB
#include <bits/stdc++.h> using namespace std; #define pii pair<int, int> #define pipii pair<int, pii> #define pipi pair<pii, pii> #pragma GCC optimize("Ofast") int N = 1<<19 ; vector<vector<int>> bin(2*N, vector<int>(1, 0)); vector<vector<int>> bleft(2*N, vector<int>(1, -1)); vector<vector<int>> bright(2*N, vector<int>(1, -1)); int K = 19; void update(int a, int b) { a += N; while (a) { int curr = 0; for (int i = K; i >= 0; i--) { bin[a][curr]++; if (b&(1<<i)) { if (bright[a][curr]==-1) { bright[a][curr] = bin[a].size(); curr = bin[a].size(); bin[a].push_back(0); bleft[a].push_back(-1); bright[a].push_back(-1); } else { curr = bright[a][curr]; } } else { if (bleft[a][curr]==-1) { bleft[a][curr] = bin[a].size(); curr = bin[a].size(); bin[a].push_back(0); bleft[a].push_back(-1); bright[a].push_back(-1); } else { curr = bleft[a][curr]; } } } a/=2; } } int query(int a, int b) { int sol = 0; int curr = 1; a++; b++; for (int i = K; i >= 0; i--) { if (a&(1<<i)) { int curr2 = 0; for (int j = K; j >= 0; j--) { if (b&(1<<j)) { if (bleft[curr][curr2]!=-1) sol += bin[curr][bleft[curr][curr2]]; if (bright[curr][curr2]==-1) break; curr2 = bright[curr][curr2]; } else { if (bleft[curr][curr2]==-1) break; curr2 = bleft[curr][curr2]; } } curr++; } curr*=2; } return sol; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, q; cin >> n >> q; vector<pipii> scores(n); map<int, int> comp; set<int> coord; for (int i = 0; i < n; i++) { int a, b; cin >> a >> b; scores[i] = {a+b, {a, b}}; coord.insert(a); coord.insert(b); } sort(scores.begin(), scores.end(), greater<pipii>()); vector<pipi> queries(q); for (int i = 0; i < q; i++) { int a, b, c; cin >> a >> b >> c; queries[i] = {{c, i}, {a, b}}; coord.insert(a); coord.insert(b); } sort(queries.begin(), queries.end(), greater<pipi>()); int d = coord.size()+K; for (int ele:coord) { comp[ele] = d--; } vector<int> sol(q); int curr = 0; for (auto ele:queries) { while (curr < scores.size() && scores[curr].first>= ele.first.first) { update(comp[scores[curr].second.first], comp[scores[curr].second.second]); //cout << comp[scores[curr].second.first] << " " << comp[scores[curr].second.second] << endl; curr++; } //cout << 1 << " " << comp[ele.second.first] << " " << comp[ele.second.second] << endl; sol[ele.first.second] = query(comp[ele.second.first], comp[ele.second.second]); } for (int ele:sol) cout << ele << "\n"; return 0; }

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:131:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         while (curr < scores.size() && scores[curr].first>= ele.first.first)
      |                ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...