oj.uz

Submission #794331

# Submission time Handle Problem Language Result Execution time Memory
794331 2023-07-26T12:51:01 Z TahirAliyev Stranded Far From Home (BOI22_island) C++17
15 / 100
 260 ms 19060 KB 
#include <bits/stdc++.h>
 
#pragma GCC optimize("O3")
 
using namespace std;
 
#define ll long long int
#define oo 4e18
#define pii pair<int, int>

const int MAX = 2e5 + 5;

ll Presum[MAX];
int arr[MAX];
int ans[MAX];

int main(){
    int n, m; cin >> n >> m;
    vector<pii> v;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
        Presum[i] = Presum[i - 1] + arr[i];
        v.push_back({arr[i], i});
    }
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    for (int i = 0; i < m; i++)
    {
        int a, b; cin >> a >> b;
    }
    set<int> s;
    s.insert(0);
    s.insert(n + 1);
    s.insert(v[0].second);
    ans[v[0].second] = 1;
    v.erase(v.begin());
    
    for(pii &a: v){
        auto itr = s.upper_bound(a.second);
        int l = (*(prev(itr)));
        int r = (*itr);
        s.insert(a.second);
        ll sum = Presum[r - 1] - Presum[l];
        if((sum >= arr[l] && ans[l]) || (sum >= arr[r] && ans[r])){
            ans[a.second] = 1;
            continue;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        cout << ans[i];
    }
    
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 2 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 206 ms 14560 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 260 ms 14424 KB Output is correct
3 Correct 238 ms 18992 KB Output is correct
4 Correct 231 ms 19000 KB Output is correct
5 Correct 170 ms 16616 KB Output is correct
6 Correct 239 ms 19012 KB Output is correct
7 Correct 211 ms 18996 KB Output is correct
8 Correct 226 ms 19060 KB Output is correct
9 Correct 183 ms 18056 KB Output is correct
10 Correct 182 ms 18356 KB Output is correct
11 Correct 177 ms 16868 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 203 ms 14432 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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