QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#464993#7969. 套娃propane#TL 1ms6108kbC++203.5kb2024-07-06 16:41:462024-07-06 16:41:47

Judging History

你现在查看的是最新测评结果

  • [2024-07-06 16:41:47]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:6108kb
  • [2024-07-06 16:41:46]
  • 提交

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);
}

}

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));
        if (mn <= i){
            if (mn > last[a[i] + 1]){
                seg[a[i] + 1].push_back({mn, i});
                // cout << mn << ' ' << i << ' ' << a[i] + 1 << '\n';
            }
            for(int j = a[i] + 1; j <= n; j++){
                int cur = last[j];
                if (cur == -1) continue;
                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);
    }
    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: 1ms
memory: 6108kb

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: 5452kb

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
Time Limit Exceeded

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:


result: