제출 #1078831

#제출 시각아이디문제언어결과실행 시간메모리
1078831Halym2007서열 (APIO23_sequence)C++17
0 / 100
2058 ms69824 KiB
#include <bits/stdc++.h> //#include "sequence.h" using namespace std; #define ll long long #define sz size() #define ff first #define ss second #define pb push_back #define pii pair <int, int> const int N = 5e5 + 5; const int NN = N * 4; int a[N], n; vector <int> idx[N]; ll mx[NN], mn[NN], st[NN], gosh[NN], jogg; void build (int ind, int l, int r) { if (l == r) { st[ind] = mn[ind] = mx[ind] = l; return; } int mid = (l + r) / 2; build (ind * 2, l, mid); build (ind * 2 + 1, mid + 1, r); mn[ind] = min (mn[ind * 2], mn[ind * 2 + 1]); mx[ind] = max (mx[ind * 2], mx[ind * 2 + 1]); } void update (int ind, int l, int r, int x, int y, ll val) { if (gosh[ind / 2]) { gosh[ind] += gosh[ind / 2]; st[ind] += (r - l + 1) * gosh[ind / 2]; mn[ind] += (r - l + 1) * gosh[ind / 2]; mx[ind] += (r - l + 1) * gosh[ind / 2]; } if (x > r or l > y) { return; } if (x <= l and r <= y) { gosh[ind] += val; st[ind] += (r - l + 1) * val; mn[ind] += (r - l + 1) * val; mx[ind] += (r - l + 1) * val; return; } int mid = (l + r) / 2; update (ind * 2, l, mid, x, y, val); update (ind * 2 + 1, mid + 1, r, x, y, val); gosh[ind] = 0; st[ind] = st[ind * 2] + st[ind * 2 + 1]; mn[ind] = min (mn[ind * 2], mn[ind * 2 + 1]); mx[ind] = max (mx[ind * 2], mx[ind * 2 + 1]); } void uly (int ind, int l, int r, int x, int y) { if (gosh[ind / 2]) { gosh[ind] += gosh[ind / 2]; st[ind] += (r - l + 1) * gosh[ind / 2]; mn[ind] += (r - l + 1) * gosh[ind / 2]; mx[ind] += (r - l + 1) * gosh[ind / 2]; } if (x > r or l > y) { return; } if (x <= l and r <= y) { jogg = max (jogg, mx[ind]); return; } int mid = (l + r) / 2; uly (ind * 2, l, mid, x, y); uly (ind * 2 + 1, mid + 1, r, x, y); gosh[ind] = 0; st[ind] = st[ind * 2] + st[ind * 2 + 1]; mn[ind] = min (mn[ind * 2], mn[ind * 2 + 1]); mx[ind] = max (mx[ind * 2], mx[ind * 2 + 1]); } void kici (int ind, int l, int r, int x, int y) { if (gosh[ind / 2]) { gosh[ind] += gosh[ind / 2]; st[ind] += (r - l + 1) * gosh[ind / 2]; mn[ind] += (r - l + 1) * gosh[ind / 2]; mx[ind] += (r - l + 1) * gosh[ind / 2]; } if (x > r or l > y) { return; } if (x <= l and r <= y) { jogg = min (jogg, mn[ind]); return; } int mid = (l + r) / 2; kici (ind * 2, l, mid, x, y); kici (ind * 2 + 1, mid + 1, r, x, y); gosh[ind] = 0; st[ind] = st[ind * 2] + st[ind * 2 + 1]; mn[ind] = min (mn[ind * 2], mn[ind * 2 + 1]); mx[ind] = max (mx[ind * 2], mx[ind * 2 + 1]); } int sequence(int N, vector<int> A) { n = N; for (int i = 0; i < n; ++i) { a[i] = A[i]; idx[a[i]].pb (i + 1); } // for (int pos : idx[1]) { // cout << pos << " "; // } // exit(0); int jogap = 0; int l = 1, r = n, jog = 1; while (l <= r) { int md = (l + r) / 2; // md = 4; // cout << md << "\n"; bool bolya = 0; build (1, 1, n); for (int i = 1; i <= n; ++i) { gosh[i] = 0; } for (int i = 1; i <= n; ++i) { for (int pos : idx[i]) {//suwagt value-sy 1 bolup dur 0 owurmeli update (1, 1, n, pos, n, -1); } for (int pos : idx[i - 1]) {// suwagt value-sy 0 bolup dur -1 owurmeli update (1, 1, n, pos, n, -1); } for (int j = 0; j + md - 1 < (int)idx[i].sz; ++j) { ll a1, a2, b1, b2; // jogg = -1e18; uly (1, 1, n, idx[i][j + md - 1], n); a2 = jogg; jogg = 1e18; kici(1, 1, n, idx[i][j + md - 1], n); a1 = jogg; jogg = -1e18; uly (1, 1, n, 1, idx[i][j]); b2 = jogg; jogg = 1e18; kici (1, 1, n, 1, idx[i][j]); b1 = jogg; if ((a1 <= b1 and b1 <= a2) or (b1 <= a1 and a1 <= b2)) { bolya = 1; break; } int jj = max (a1, b1), jj1 = min(a2, b2); if ((jj <= md + jj1)) { bolya = 1; // cout << "men\n"; // cout << a1 << " " << b1 << " " << a2 << "\n"; // cout << b1 << " " << a1 << " " << b2 << "\n"; // cout << "men " << idx[i][j] << " " << idx[i][j + md - 1] << " " << i; // exit(0); break; } } if (bolya) break; } // cout << bolya << "\n"; // cout << "gutar\n"; // exit(0); if (bolya) { l = md + 1; jog = md; } else { r = md - 1; } } return jog; } // a[i]>=1 and a[i] <= n //int main() { // freopen ("input.txt", "r", stdin); // int N; // assert(1 == scanf("%d", &N)); // // std::vector<int> A(N); // for (int i = 0; i < N; ++i) { // assert(1 == scanf("%d", &A[i])); // } // int result = sequence(N, A); // printf("%d\n", result); // return 0; //} /* 9 1 1 2 3 4 3 2 1 1 answer : 2 7 1 2 3 1 2 1 3 answer : 3 14 2 6 2 5 3 4 2 1 4 3 5 6 3 2 answer : 3 */

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

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:115:6: warning: unused variable 'jogap' [-Wunused-variable]
  115 |  int jogap = 0;
      |      ^~~~~
#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...