QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #465027 | #7969. 套娃 | propane# | WA | 39ms | 19604kb | C++20 | 4.5kb | 2024-07-06 16:59:44 | 2024-07-06 16:59:45 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<array>
#include<tuple>
#include<algorithm>
using namespace std;
using LL = long long;
const int maxn = 1e5 + 5, INF = 0x3f3f3f3f;
namespace SGT1{
int tr[maxn * 4];
void modify(int u, int l, int r, int x, int v){
if (l == r){
tr[u] = v;
return;
}
int mid = (l + r) / 2;
if (x <= mid) modify(2 * u, l, mid, x, v);
else modify(2 * u + 1, mid + 1, r, x, v);
tr[u] = min(tr[2 * u], tr[2 * u + 1]);
}
int query(int u, int l, int r, int L, int R){
if (l > R or r < L) return INF;
if (l >= L and r <= R) return tr[u];
int mid = (l + r) / 2;
return min(query(2 * u, l, mid, L, R), query(2 * u + 1, mid + 1, r, L, R));
}
}
namespace SGT2{
int tr[maxn * 4];
void modify(int u, int l, int r, int x, int v){
if (l == r){
tr[u] += v;
return;
}
int mid = (l + r) / 2;
if (x <= mid) modify(2 * u, l, mid, x, v);
else modify(2 * u + 1, mid + 1, r, x, v);
tr[u] = min(tr[2 * u], tr[2 * u + 1]);
}
int find_first(int u, int l, int r){
if (l == r) return r;
int mid = (l + r) / 2;
if (tr[2 * u] == 0) return find_first(2 * u, l, mid);
return find_first(2 * u + 1, mid + 1, r);
}
}
namespace SGT3{
int tr[maxn * 4];
void modify(int u, int l, int r, int x, int v){
if (l == r){
tr[u] = v;
return;
}
int mid = (l + r) / 2;
if (x <= mid) modify(2 * u, l, mid, x, v);
else modify(2 * u + 1, mid + 1, r, x, v);
tr[u] = min(tr[2 * u], tr[2 * u + 1]);
}
int find_first(int u, int l, int r, int pos){
if (l == r) return r;
int mid = (l + r) / 2;
if (tr[2 * u] < pos) return find_first(2 * u, l, mid, pos);
return find_first(2 * u + 1, mid + 1, r, pos);
}
}
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n;
cin >> n;
vector<int> a(n + 1), last(n + 2);
vector<vector<int> > pos(n + 1);
for(int i = 0; i <= n; i++){
pos[i].push_back(0);
}
vector<vector<pair<int, int> > > seg(n + 2);
memset(SGT1::tr, 0x3f, sizeof SGT1::tr);
for(int i = 1; i <= n; i++){
cin >> a[i];
int mn = (a[i] == 0 ? i : SGT1::query(1, 0, n, 0, a[i] - 1));
SGT3::modify(1, 0, n, a[i], i);
// int cnt = 0;
if (mn <= i){
if (mn > last[a[i] + 1]){
seg[a[i] + 1].push_back({mn, i});
// cnt += 1;
// cout << mn << ' ' << i << ' ' << a[i] + 1 << '\n';
}
for(int j = a[i] + 1; j <= n; ){
// cnt += 1;
int cur = last[j];
if (cur == 0) break;
mn = min(mn, cur);
if (mn < last[a[i]]) break;
int mex = SGT3::find_first(1, 0, n, mn);
seg[mex].push_back({mn, i});
j = mex;
// int nxt = last[j + 1];
// mn = min(mn, cur);
// if (mn > nxt){
// int l = min(mn, last[j]);
// seg[j + 1].push_back({l, i});
// // cout << l << ' ' << i << ' ' << j + 1 << '\n';
// }
}
}
last[a[i]] = i;
pos[a[i]].push_back(i);
SGT1::modify(1, 0, n, a[i], i);
// cout << cnt << '\n';
}
for(int i = 0; i <= n; i++){
pos[i].push_back(n + 1);
}
vector<vector<pair<int, int> > > q(n + 1);
{
for(int i = 0; i + 1 < pos[0].size(); i++){
int len = pos[0][i + 1] - pos[0][i] - 1;
q[1].push_back({0, 1});
if (len + 1 <= n) q[len + 1].push_back({0, -1});
}
}
for(int i = 1; i <= n; i++){
if (seg[i].empty()) continue;
vector<pair<int, int> > p;
for(auto [l, r] : seg[i]){
int pre = *prev(lower_bound(pos[i].begin(), pos[i].end(), l));
int nxt = *upper_bound(pos[i].begin(), pos[i].end(), r);
int len = nxt - pre - 1;
q[r - l + 1].push_back({i, 1});
if (len + 1 <= n) q[len + 1].push_back({i, -1});
}
}
for(int i = 1; i <= n; i++){
for(auto [x, v] : q[i]){
SGT2::modify(1, 0, n, x, v);
}
cout << SGT2::find_first(1, 0, n) << ' ';
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5948kb
input:
6 0 0 0 1 2 3
output:
2 3 4 0 0 0
result:
ok single line: '2 3 4 0 0 0 '
Test #2:
score: 0
Accepted
time: 1ms
memory: 5164kb
input:
100 0 10 21 9 4 1 14 0 8 1 4 6 10 0 0 4 18 0 12 5 2 5 15 1 6 2 0 4 14 5 1 2 23 1 8 1 24 8 8 9 5 2 12 2 3 7 6 11 12 12 6 12 4 4 5 0 7 4 9 12 1 7 4 7 12 2 10 2 4 8 7 1 4 0 13 9 13 2 2 3 9 14 7 9 15 10 10 6 2 12 3 11 6 3 4 7 9 6 11 1
output:
2 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 2 2 2 2 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok single line: '2 2 3 4 4 4 4 4 4 4 4 4 4 4 4 ... 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 '
Test #3:
score: -100
Wrong Answer
time: 39ms
memory: 19604kb
input:
100000 127 145 474 139 36 135 75 670 76 433 206 214 283 56 214 440 147 280 244 190 181 565 31 550 261 93 526 404 125 390 17 552 5 364 53 337 52 506 277 279 15 248 46 61 826 69 166 297 171 289 150 175 111 151 317 342 166 13 199 152 308 19 156 347 205 166 45 115 177 235 422 425 109 4 658 232 347 370 4...
output:
2 2 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 ...
result:
wrong answer 1st lines differ - expected: '2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0', found: '2 2 3 3 3 4 4 4 4 4 4 4 4 4 4 ... 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 '