제출 #569182

#제출 시각아이디문제언어결과실행 시간메모리
569182aryan12가로등 (APIO19_street_lamps)C++17
0 / 100
339 ms207648 KiB
#include <bits/stdc++.h> using namespace std; #define int long long mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); const int N = 5e5 + 5; int DP[20][N]; struct node { int max_par, value, depth; } *reach_tree[N * 2]; int Find(int x) { if(x == reach_tree[x]->max_par) { return x; } return reach_tree[x]->max_par = Find(reach_tree[x]->max_par); } void Unite(int a, int b, int x, int val) { a = Find(a), b = Find(b); // cout << "Uniting: " << a << ", " << b << ", to: (" << x << ", " << val << ")\n"; DP[0][a] = x; DP[0][b] = x; reach_tree[a]->max_par = x; reach_tree[b]->max_par = x; reach_tree[x]->value = val; } int LCA(int x, int y, int omk) { int ok_x = x, ok_y = y; int depth_x = 1, depth_y = 1; for(int i = 19; i >= 0; i--) { if(DP[i][ok_x] != omk) { ok_x = DP[i][ok_x]; depth_x += (1 << i); } if(DP[i][ok_y] != omk) { ok_y = DP[i][ok_y]; depth_y += (1 << i); } } if(depth_x > depth_y) { swap(x, y); swap(depth_x, depth_y); } int diff = depth_y - depth_x; for(int i = 19; i >= 0; i--) { if((1 << i) & diff) { y = DP[i][y]; } } if(x == y) return x; for(int i = 19; i >= 0; i--) { if(DP[i][x] != DP[i][y]) { x = DP[i][x]; y = DP[i][y]; } } return DP[0][x]; } void Solve() { int n, q; cin >> n >> q; for(int i = 0; i <= (n + 1) * 2; i++) { reach_tree[i] = new node(); DP[0][i] = i; reach_tree[i]->max_par = i; reach_tree[i]->value = 0; } // vector<array<int, 2> > a(n + 1, {0, -1}); // alr occurred, start pos (start pos = -1 if off) string s; cin >> s; int next_one = n + 1; for(int i = 0; i < n; i++) { if(s[i] == '1') { // cout << "i = " << i << ", i + 1 = " << i + 1 << "\n"; Unite(i, i + 1, next_one++, 0LL); } } vector<array<int, 3> > queries; for(int i = 1; i <= q; i++) { string command; cin >> command; if(command == "query") { int a, b; cin >> a >> b; a--, b--; queries.push_back({a, b, i}); } else { int idx; cin >> idx; idx--; Unite(idx, idx + 1, next_one++, i); } } for(int i = 1; i < 20; i++) { for(int j = 0; j < next_one; j++) { DP[i][j] = DP[i - 1][DP[i - 1][j]]; } } // for(int i = 0; i < 20; i++) // { // for(int j = 0; j < next_one; j++) // { // cout << DP[i][j] << " "; // } // cout << "\n"; // } for(int i = 0; i < queries.size(); i++) { int lca = LCA(queries[i][0], queries[i][1], next_one - 1); // cout << "lca = " << lca << "\n"; cout << max(0LL, queries[i][2] - reach_tree[lca]->value) << "\n"; } } int32_t main() { auto begin = std::chrono::high_resolution_clock::now(); ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; for(int i = 1; i <= t; i++) { //cout << "Case #" << i << ": "; Solve(); } auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

street_lamps.cpp: In function 'void Solve()':
street_lamps.cpp:135:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |  for(int i = 0; i < queries.size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...