Submission #120137

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
120137	2019-06-23 14:11:45	E869120	Editor (BOI15_edi)	C++14	100 / 100	706 ms	58656 KiB

edi

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <algorithm>
using namespace std;
int N, A[1 << 19], dp[1 << 19][22], ret[1 << 19], dp2[1 << 19][22];
int main() {
  cin >> N;
  for (int i = 1; i <= N; i++) {
    cin >> A[i];
    if (A[i] > 0) { for (int j = 0; j <= 21; j++) { dp[i][j] = i; dp2[i][j] = 0; } ret[i] = A[i]; }
    else {
      int cx = i - 1, level = -A[i];
      for (int j = 21; j >= 0; j--) {
        if (dp2[cx][j] >= level) cx = dp[cx][j];
      }
      cx--;
      if (cx == 0) { ret[i] = 0; for (int j = 0; j <= 21; j++) dp2[i][j] = level; }
      else {
        ret[i] = ret[cx];
        dp[i][0] = cx; dp2[i][0] = level;
        for (int j = 1; j <= 21; j++) {
          dp[i][j] = dp[dp[i][j - 1]][j - 1];
          dp2[i][j] = min(dp2[i][j - 1], dp2[dp[i][j - 1]][j - 1]);
        }
      }
    }
  }
  for (int i = 1; i <= N; i++) cout << ret[i] << endl;
  return 0;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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