oj.uz

Submission #787291

# Submission time Handle Problem Language Result Execution time Memory
787291 2023-07-19T03:48:21 Z burythelightdeepwithin Editor (BOI15_edi) C++14
15 / 100
 3000 ms 6948 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 718 ms 6948 KB Output is correct
2 Correct 805 ms 6848 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3068 ms 3208 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -