oj.uz

Submission #823740

# Submission time Handle Problem Language Result Execution time Memory
823740 2023-08-13T04:17:18 Z peteza Stranded Far From Home (BOI22_island) C++14
15 / 100
 39 ms 19584 KB 
#include <bits/stdc++.h>
using namespace std;

int n, m;
int s[200005];
int ans[200005];

struct node {
    int idx=0;
    long long sum = 0;
    node *l, *r;
    node(int x):l(0),r(0),sum(s[x]),idx(x){}
};
stack<node*> curs;
node* root;

long long dfssum(node* cur) {
    if(!cur) return 0;
    return cur->sum = dfssum(cur->l) + dfssum(cur->r) + s[cur->idx];
}

void dfsans(node *cur, long long parsum = -1, bool parres = 1) {
    if(!cur) return;
    ans[cur->idx] = ((cur->sum) >= parsum && parres);
    dfsans(cur->l, s[cur->idx], ans[cur->idx]);
    dfsans(cur->r, s[cur->idx], ans[cur->idx]);
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++) {
        cin >> s[i];
        auto neu = new node(i);
        while(!curs.empty() && s[curs.top()->idx] < s[i]) {
            curs.top()->r = neu->l;
            neu->l = curs.top();
            curs.pop();
        }
        curs.push(neu);
    }
    root = curs.top(); curs.pop();
    while(!curs.empty()) {
        curs.top()->r = root;
        root = curs.top(); curs.pop();
    }
    dfssum(root); dfsans(root);
    for(int i=1;i<=n;i++) cout << ans[i];
}

Compilation message

island.cpp: In constructor 'node::node(int)':
island.cpp:11:15: warning: 'node::r' will be initialized after [-Wreorder]
   11 |     node *l, *r;
      |               ^
island.cpp:10:15: warning:   'long long int node::sum' [-Wreorder]
   10 |     long long sum = 0;
      |               ^~~
island.cpp:12:5: warning:   when initialized here [-Wreorder]
   12 |     node(int x):l(0),r(0),sum(s[x]),idx(x){}
      |     ^~~~
island.cpp:10:15: warning: 'node::sum' will be initialized after [-Wreorder]
   10 |     long long sum = 0;
      |               ^~~
island.cpp:9:9: warning:   'int node::idx' [-Wreorder]
    9 |     int idx=0;
      |         ^~~
island.cpp:12:5: warning:   when initialized here [-Wreorder]
   12 |     node(int x):l(0),r(0),sum(s[x]),idx(x){}
      |     ^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 35 ms 17484 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 35 ms 11352 KB Output is correct
3 Correct 36 ms 13620 KB Output is correct
4 Correct 36 ms 19584 KB Output is correct
5 Correct 27 ms 15492 KB Output is correct
6 Correct 36 ms 13608 KB Output is correct
7 Correct 39 ms 17988 KB Output is correct
8 Correct 35 ms 17952 KB Output is correct
9 Correct 31 ms 18696 KB Output is correct
10 Correct 31 ms 15936 KB Output is correct
11 Correct 28 ms 13136 KB Output is correct

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -