제출 #933189

#제출 시각아이디문제언어결과실행 시간메모리
933189Sharky서열 (APIO23_sequence)C++17
0 / 100
1180 ms71252 KiB
#include "sequence.h" #include <bits/stdc++.h> using namespace std; const int N = 500050; int ans = 1; // if in range >= 0: segtree 1s = find min. struct MaxSegTree { int size = 1; vector<int> seg, lazy; void init(int n) { while (size < n) size *= 2; seg.assign(2 * size + 5, 0); lazy.assign(2 * size + 5, 0); } void push(int id) { seg[id] += lazy[id]; if (id < size) { for (int i = 0; i < 2; i++) { lazy[id * 2 + i] += lazy[id]; continue; } } lazy[id] = 0; } void pull(int id) { seg[id] = max(seg[id * 2], seg[id * 2 + 1]); } void build(int l, int r, int id, vector<int>& v) { if (l == r) { seg[id] = v[l]; return; } int mid = (l + r) / 2; build(l, mid, id * 2, v); build(mid + 1, r, id * 2 + 1, v); pull(id); } void upd(int ql, int qr, int val, int l, int r, int id) { push(id); if (qr < l || r < ql) return; if (ql <= l && r <= qr) { push(id); lazy[id] = val; return; } int mid = (l + r) / 2; upd(ql, qr, val, l, mid, id * 2); upd(ql, qr, val, mid + 1, r, id * 2 + 1); pull(id); } int qry(int ql, int qr, int l, int r, int id) { push(id); if (qr < l || r < ql) return 0; if (ql <= l && r <= qr) return seg[id]; int mid = (l + r) / 2; return max(qry(ql, qr, l, mid, id * 2), qry(ql, qr, mid + 1, r, id * 2 + 1)); } } pref0, suff0; struct MinSegTree { int size = 1; vector<int> seg, lazy; void init(int n) { while (size < n) size *= 2; seg.assign(2 * size + 5, 0); lazy.assign(2 * size + 5, 0); } void push(int id) { seg[id] += lazy[id]; if (id < size) { for (int i = 0; i < 2; i++) { lazy[id * 2 + i] += lazy[id]; continue; } } lazy[id] = 0; } void pull(int id) { seg[id] = min(seg[id * 2], seg[id * 2 + 1]); } void build(int l, int r, int id, vector<int>& v) { if (l == r) { seg[id] = v[l]; return; } int mid = (l + r) / 2; build(l, mid, id * 2, v); build(mid + 1, r, id * 2 + 1, v); pull(id); } void upd(int ql, int qr, int val, int l, int r, int id) { push(id); if (qr < l || r < ql) return; if (ql <= l && r <= qr) { push(id); lazy[id] = val; return; } int mid = (l + r) / 2; upd(ql, qr, val, l, mid, id * 2); upd(ql, qr, val, mid + 1, r, id * 2 + 1); pull(id); } int qry(int ql, int qr, int l, int r, int id) { push(id); if (qr < l || r < ql) return 0; if (ql <= l && r <= qr) return seg[id]; int mid = (l + r) / 2; return min(qry(ql, qr, l, mid, id * 2), qry(ql, qr, mid + 1, r, id * 2 + 1)); } } pref1, suff1; int n; bool check(int l, int r, int c) { int d = pref0.qry(r, r, 1, n, 1) - pref0.qry(l - 1, l - 1, 1, n, 1); int w = d - c; int x = 0, y = 0; if (w <= 0) x = max(0, suff0.qry(1, l - 1, 1, n, 1)), y = max(0, pref0.qry(r + 1, n, 1, n, 1)); else if (w >= 0) x = min(0, suff1.qry(1, l - 1, 1, n, 1)), y = min(0, pref1.qry(r + 1, n, 1, n, 1)); if (w <= 0 && x + y + w + c >= 0) return true; if (w >= 0 && x + y + w - c <= 0) return true; return false; } int sequence(int _n, vector<int> tmp) { n = _n; vector<int> a(n+1), ps(n+1, 0); vector<vector<int>> pos(n+1); for (int i = 1; i <= n; i++) { a[i] = tmp[i - 1]; pos[a[i]].push_back(i); } pref0.init(n + 1); suff0.init(n + 1); pref1.init(n + 1); suff1.init(n + 1); for (int i = 1; i <= n; i++) ps[i] = i; pref0.build(1, n, 1, ps); pref1.build(1, n, 1, ps); for (int i = 1; i <= n; i++) ps[i] = n - i + 1; suff0.build(1, n, 1, ps); suff1.build(1, n, 1, ps); for (int i = 1; i <= n; i++) { int l = 0, r = 0; for (int j = 0; j < pos[i].size(); j++) { pref1.upd(pos[i][j], n, -2, 1, n, 1); suff1.upd(1, pos[i][j], -2, 1, n, 1); } while (r < pos[i].size()) { if (check(pos[i][l], pos[i][r], r - l + 1)) r++; else l++; ans = max(ans, r - l); } for (int j = 0; j < pos[i].size(); j++) { pref0.upd(pos[i][j], n, -2, 1, n, 1); suff0.upd(1, pos[i][j], -2, 1, n, 1); } } return ans; }

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

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:145:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |         for (int j = 0; j < pos[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~
sequence.cpp:149:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |         while (r < pos[i].size()) {
      |                ~~^~~~~~~~~~~~~~~
sequence.cpp:154:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |         for (int j = 0; j < pos[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~
#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...