Submission #787291

#	Time	Username	Problem	Language	Result	Execution time	Memory
787291		burythelightdeepwithin	Editor (BOI15_edi)	C++14	15 / 100	3068 ms	6948 KiB

edi

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5+7;
pair <char, int> op[N];
pair <int, int> link[N];
int n;

int main(){
    cin >> n;
    op[0] = {'E', 0};
    link[0] = {1, 0};
    for (int i = 1; i <= n; i++){
        int w;
        cin >> w;
        if (w < 0){
            op[i] = {'U', -w};
        } else {
            op[i] = {'E', w};
        }
    }
    //cout << "\n";
    for (int i = 1; i <= n; i++){
        if (op[i].first == 'E'){
            cout << op[i].second << "\n";
            link[i] = {1, 0};
        } else {
            int lv = op[i].second;
            for (int j = i-1; j >= 1; j--){
                if (link[j].first == 1 && (op[j].first == 'E' || (op[j].first == 'U' && op[j].second < lv))){
                    link[i] = {1, j};
                    break;
                }
            }
            int ptr = link[i].second, w = ptr;
            while(ptr != 0){
                //cout << ptr << ' ';
                link[ptr].first = 1 - link[ptr].first;
                //cout << link[ptr].first << "\n";
                w = ptr;
                ptr = link[ptr].second;
            }
            link[i].second = w;
            //cout << "PTR\n";
            for (int j = i; j >= 0; j--){
                if (op[j].first == 'E' && link[j].first == 1){
                    cout << op[j].second << "\n";
                    break;
                }
            }
        }
    }
}


/*
11
1
2
5
-1
-1
-3
-4
4
-2
-1
1
*/


/*
1
2
5
3 PTR
2
2 PTR
1
5 2 PTR
2
6 5 2 PTR
1
4
8 PTR
1
1 PTR
0
1
*/

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