Submission #823740

#	Time	Username	Problem	Language	Result	Execution time	Memory
823740		peteza	Stranded Far From Home (BOI22_island)	C++14	15 / 100	39 ms	19584 KiB

island

#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 (stderr)

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
• Subtask 2: 0 / 10
• Subtask 3: 15 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35