제출 #752337

#제출 시각아이디문제언어결과실행 시간메모리
752337aryan12서열 (APIO23_sequence)C++17
0 / 100
364 ms56236 KiB
#include "sequence.h" #include <bits/stdc++.h> using namespace std; #define int long long const int N = 5e5 + 5, INF = 1e18; pair<int, int> seg[N * 4]; int lazy[N * 4]; void UpdateLazy(int l, int r, int pos) { if(l == r) { seg[pos].first += lazy[pos]; seg[pos].second += lazy[pos]; lazy[pos] = 0; return; } seg[pos].first += lazy[pos]; seg[pos].second += lazy[pos]; lazy[pos * 2] += lazy[pos]; lazy[pos * 2 + 1] += lazy[pos]; lazy[pos] = 0; } void Build(int l, int r, int pos) { seg[pos] = {-r, -l}; if(l == r) return; int mid = (l + r) / 2; Build(l, mid, pos * 2); Build(mid + 1, r, pos * 2 + 1); } void Update(int l, int r, int pos, int ql, int qval) { if(lazy[pos] != 0) { UpdateLazy(l, r, pos); } if(ql > r) { // cout << "Update(" << l << ", " << r << ") out of bounds\n"; return; } if(l == r) { // cout << "Update(" << l << ", " << r << ") total in [1]\n"; seg[pos].first += qval; seg[pos].second += qval; return; } if(l >= ql) { // cout << "Update(" << l << ", " << r << ") total in [2]\n"; seg[pos].first += qval; seg[pos].second += qval; lazy[pos * 2] += qval; lazy[pos * 2 + 1] += qval; return; } int mid = (l + r) / 2; Update(l, mid, pos * 2, ql, qval); Update(mid + 1, r, pos * 2 + 1, ql, qval); // cout << "Update(" << l << ", " << r << ") partial\n"; seg[pos].first = min(seg[pos * 2].first, seg[pos * 2 + 1].first); seg[pos].second = max(seg[pos * 2].second, seg[pos * 2 + 1].second); } pair<int, int> Query(int l, int r, int pos, int ql, int qr) { if(lazy[pos] != 0) { UpdateLazy(l, r, pos); } if(ql <= l && r <= qr) { return seg[pos]; } if(ql > r || l > qr) { return {INF, -INF}; } int mid = (l + r) / 2; pair<int, int> p1 = Query(l, mid, pos * 2, ql, qr); pair<int, int> p2 = Query(mid + 1, r, pos * 2 + 1, ql, qr); return {min(p1.first, p2.first), max(p1.second, p2.second)}; } int32_t sequence(int32_t n, vector<int32_t> a) { Build(1, n, 1); vector<int> occ[n + 1]; for(int i = 0; i < a.size(); i++) { occ[a[i]].push_back(i + 1); } int ans = 1; for(int i = 1; i <= n; i++) { if(occ[i].size() == 0) continue; if(occ[i].size() == 1) { Update(1, n, 1, occ[i][0], 2); continue; } // cout << "occ[i] = {" << occ[i][0] << ", " << occ[i][1] << "}\n"; // cout << "Updating: [" << occ[i][0] << ", " << n << "]\n"; Update(1, n, 1, occ[i][0], 1); // cout << "Updating: [" << occ[i][1] << ", " << n << "]\n"; Update(1, n, 1, occ[i][1], 1); pair<int, int> p1 = Query(1, n, 1, 1, occ[i][0] - 1); if(occ[i][0] == 1) { p1 = {0, 0}; } pair<int, int> p2 = Query(1, n, 1, occ[i][1], n); // cout << p1.first << " " << p1.second << " " << p2.first << " " << p2.second << "\n"; if(p2.first + 2 >= p1.first && p2.first - 2 <= p1.second) { ans = 2; } if(p2.second + 2 >= p1.first && p2.second - 2 <= p1.second) { ans = 2; } // cout << "ans = " << ans << "\n"; Update(1, n, 1, occ[i][0], 1); Update(1, n, 1, occ[i][1], 1); } return ans; }

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

sequence.cpp: In function 'int32_t sequence(int32_t, std::vector<int>)':
sequence.cpp:94:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int i = 0; i < a.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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...