Submission #1274645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274645		behesht	Editor (BOI15_edi)	C++20	100 / 100	291 ms	155048 KiB

edi

#include <bits/stdc++.h>

#define d1(x)                cout << #x << " : " << x << endl << flush
#define d2(x, y)             cout << #x << " : " << x << "   " << #y << " : " << y << endl << flush
#define d3(x, y, z)          cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << endl << flush
#define d4(x, y, z, a)       cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << "    "<< #a << " : " << a << endl << flush
#define arr(x)               array <ll, x>
#define ld                   long double
#define ll                   long long
#define int                  long long
#define pb                   push_back
#define endl                 '\n'
#define lc                   v << 1
#define rc                   v << 1 | 1

using namespace std;

const int INF = 1e9 + 24 + (34 / 10); // 34 ---> 35
const int MAXN = 3e5 + 24 + (34 / 10); // 34 ---> 35
const int LOG = 31;

int dp[MAXN], st[MAXN][LOG], bl[MAXN][LOG];
int a[MAXN], lv[MAXN];

signed main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	for(int i = 1; i <= n; i++){
		cin >> a[i];
		int u = i;

		if(a[i] > 0){
			dp[i] = a[i];
			st[i][0] = 0;
			bl[i][0] = i - 1;
			lv[i] = 0;
		}

		else{
			lv[i] = -a[i];
			u = i - 1;

			for(int bt = LOG - 1; bt >= 0; bt--)
				if(st[u][bt] >= lv[i])
					u = bl[u][bt];

			bl[i][0] = u - 1;
			st[i][0] = lv[i];
			dp[i] = dp[u - 1];
		}

		for(int bt = 1; bt < LOG; bt++)
			bl[i][bt] = bl[bl[i][bt - 1]][bt - 1];

		for(int bt = 1; bt < LOG; bt++)
			st[i][bt] = min(st[i][bt - 1], st[bl[i][bt - 1]][bt - 1]);

		// d3(i, u, dp[i]);

		cout << dp[i] << endl;
	}
}

// Ey To Bahane! :_)))

// -------------<3------------- //
/*
Magasan dor shirini: 

1. MAXN
2. Input style
3. index or value? Masale In Ast!	
4. MOD 

*/

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