Submission #1127331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127331		Kerim	Editor (BOI15_edi)	C++20	35 / 100	3094 ms	14380 KiB

edi

#include "bits/stdc++.h"

using namespace std;

struct edi{
    int val;
    int lvl;
    int par;
    bool active;
    edi(int _val, int _lvl){
        par = -1;
        val = _val;
        lvl = _lvl;
        active = 0;
    }
};
vector<edi> v;
const int N = 3e5+5;
int s[N<<2];
int get(int l, int r, int val, int nd, int x, int y){
    if (l > y or x > r or s[nd] >= val)
        return -1;
    if (x == y)
        return x;
    int mid = (x+y) >> 1;
    int pos = get(l, r, val, nd<<1|1, mid+1, y);
    if (~pos)
        return pos;
    return get(l, r, val, nd<<1, x, mid);
}
void upd(int pos, int nd, int x, int y){
    if (x == y){
        if (v[pos].active)
            s[nd] = v[pos].lvl;
        else
            s[nd] = 1e9;
        return;
    }
    int mid = (x+y) >> 1;
    if (pos <= mid)
        upd(pos, nd<<1, x, mid);
    else
        upd(pos, nd<<1|1, mid+1, y);
    s[nd] = min(s[nd<<1], s[nd<<1|1]);
}
void build(int nd, int x, int y){
    if (x == y){
        s[nd] = 1e9;
        return;
    }
    int mid = (x+y) >> 1;
    build(nd<<1, x, mid);
    build(nd<<1|1, mid+1, y);
}
int main(){
    // freopen("file.in", "r", stdin);
    int n;
    scanf("%d", &n);
    build(1, 0, n);
    v.push_back(edi(0, 0));
    v[0].active = 1;
    upd(0, 1, 0, n);
    for (int i = 1; i <= n; i++){
        int x;
        scanf("%d", &x);
        if (x > 0)
            v.push_back(edi(x, 0));
        else{
            v.push_back(edi(-1, -x));
            //need to be optimized
            v[i].par = get(0, i, -x, 1, 0, n);
            // for (int j = i; j >= 0; j--){
            //     if (v[j].active and v[j].lvl < v.back().lvl){
            //         v[i].par = j;
            //         break;
            //     }
            // }
        }
        //need to be optimized
        int cur = i;
        while (~cur){
            v[cur].active ^= 1;
            upd(cur, 1, 0, n);
            cur = v[cur].par;
        }

        //need to be optimized
        int ans = get(0, i, 1, 1, 0, n);
        // for (int j = i; j >= 0; j--)
        //     if (v[j].active and v[j].lvl < 1){
        //         ans = j;
        //         break;
        //     }
        printf("%d\n", v[ans].val);
    }

}

Compilation message (stderr)

edi.cpp: In function 'int main()':
edi.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
edi.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37