oj.uz

Submission #601492

# Submission time Handle Problem Language Result Execution time Memory
601492 2022-07-22T05:49:20 Z 반딧불(#8472) Stranded Far From Home (BOI22_island) C++17
15 / 100
 197 ms 44792 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree{
    pair<ll, int> tree[800002];

    void init(int i, int l, int r, ll *A){
        if(l==r){
            tree[i] = make_pair(A[l], l);
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, A);
        init(i*2+1, m+1, r, A);
        tree[i] = max(tree[i*2], tree[i*2+1]);
    }

    pair<ll, int> query(int i, int l, int r, int s, int e){
        if(r<s || e<l) return make_pair(0LL, 0);
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return max(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
    }
} tree;

int n, m;
ll arr[200002];
ll sum[200002];
bool ans[200002];
vector<int> link[200002];

void dnc(int l, int r, ll lim=0){
    if(l>r || sum[r]-sum[l-1] < lim) return;
    pair<ll, int> tp = tree.query(1, 1, n, l, r);
    int x = tp.second;
    ans[x] = 1;
    dnc(l, x-1, arr[x]);
    dnc(x+1, r, arr[x]);
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
    for(int i=1; i<=m; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        link[x].push_back(y);
        link[y].push_back(x);
    }

    tree.init(1, 1, n, arr);
    for(int i=1; i<=n; i++) sum[i] = sum[i-1] + arr[i];

    dnc(1, n);

    for(int i=1; i<=n; i++) printf("%d", ans[i]);
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
island.cpp:46:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~
island.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Incorrect 143 ms 22932 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 3 ms 4948 KB Output is correct
2 Correct 165 ms 22912 KB Output is correct
3 Correct 154 ms 22972 KB Output is correct
4 Correct 162 ms 44792 KB Output is correct
5 Correct 121 ms 22680 KB Output is correct
6 Correct 151 ms 22884 KB Output is correct
7 Correct 197 ms 33880 KB Output is correct
8 Correct 170 ms 33868 KB Output is correct
9 Correct 111 ms 22808 KB Output is correct
10 Correct 153 ms 34020 KB Output is correct
11 Correct 125 ms 22756 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 174 ms 25068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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