oj.uz

Submission #654457

# Submission time Handle Problem Language Result Execution time Memory
654457 2022-10-31T11:04:00 Z atigun Stranded Far From Home (BOI22_island) C++14
15 / 100
 338 ms 28300 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 2e5;

int n, m;
vector<ll> a(maxn+5), prefix(maxn+5, 0);
vector<vector<int>> g(maxn+5);

void solve(){
  cin >> n >> m;
  bool ok = 1;
  vector<int> ans(maxn+5, 0);
  vector<pair<int, int>> query;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
    query.push_back({a[i], i});
    prefix[i] = prefix[i-1]+a[i];
  }
  sort(query.begin(), query.end());
  set<pair<int, int>> check;
  for(int i = 1; i <= m; i++){
    int a, b;
    cin >> a >> b;
    if(a > b)
      swap(a, b);
    check.insert({a, b});
    ok&= (abs(a-b)==1);
  }
  ok&= (check.size()==n-1);
  set<pair<int, int>> regions;
  regions.insert({1, n});
  ll maxi = *max_element(a.begin(), a.end());
  for(int q = n-1; q >= 0; q--){
    // for(pair<int, int> h : regions){
    //   cout << h.first << " " << h.second << " - ";
    // }
    // cout << "\n";
    if(a[query[q].second] == maxi){
      ans[query[q].second] = 1;
    }else{
      auto itL = regions.lower_bound({query[q].second+1, -1});
      if(itL == regions.begin()){
        ans[query[q].second] = 0;
      }else{
        itL--;
        int L = itL->first, R = itL->second;
        ll sum = prefix[R] - prefix[L-1];
        if((ans[R+1] && sum >= a[R+1]) || (ans[L-1] && sum >= a[L-1]))
          ans[query[q].second] = 1;
      }
    }
    if(q-1 >= 0 && query[q-1].first != query[q].first){
      int p = q;
      while(p < n && query[p].first == query[q].first){
        // cout << p << " ";
        auto it = regions.lower_bound({query[p].second+1, -1});
        if(it != regions.begin()){
          --it;
        }else{
          p--;
          continue;
        }
        int LL = it->first, RR = it->second;
        regions.erase(it);
        int mid = query[p].second;
        if((mid-1) - LL +1 >= 1)
          regions.insert({LL, mid-1});
        if(RR - (mid+1) +1 >= 1)
          regions.insert({mid+1, RR});
        p++;
      }
      // cout << "\n";
    }
  }
  for(int i = 1; i <= n; i++)
    cout << (ans[i] && ok);
  cout << "\n";
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt = 1;
  // cin >> tt;
  while(tt--){
    solve();
  }
}

Compilation message

island.cpp: In function 'void solve()':
island.cpp:32:21: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |   ok&= (check.size()==n-1);
      |         ~~~~~~~~~~~~^~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 8916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8916 KB Output is correct
2 Correct 302 ms 22292 KB Output is correct
3 Correct 281 ms 25984 KB Output is correct
4 Correct 193 ms 23628 KB Output is correct
5 Correct 192 ms 23000 KB Output is correct
6 Correct 338 ms 25960 KB Output is correct
7 Correct 234 ms 23660 KB Output is correct
8 Correct 211 ms 23680 KB Output is correct
9 Correct 120 ms 23440 KB Output is correct
10 Correct 258 ms 28300 KB Output is correct
11 Correct 249 ms 25284 KB Output is correct

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8916 KB Output isn't correct
2 Halted 0 ms 0 KB -