oj.uz

Submission #654450

# Submission time Handle Problem Language Result Execution time Memory
654450 2022-10-31T10:41:46 Z atigun Stranded Far From Home (BOI22_island) C++14
0 / 100
 1000 ms 21400 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, -1);
  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});
  for(int q = n-1; q >= 0; q--){
    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 >= 0 && query[p].first == query[q].first){
        auto it = regions.lower_bound({query[p].second+1, -1});
        if(it != regions.begin())
          --it;
        int LL = it->first, RR = it->second;
        regions.erase(it);
        int mid = query[p].second;
        if((mid-1) - LL >= 1)
          regions.insert({LL, mid-1});
        if(RR - (mid+1) >= 1)
          regions.insert({mid+1, RR});
        p--;
      }
    }
  }
  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 Execution timed out 1084 ms 8916 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 8916 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 8916 KB Time limit exceeded
2 Halted 0 ms 0 KB -