Submission #654457

#	Time	Username	Problem	Language	Result	Execution time	Memory
654457		atigun	Stranded Far From Home (BOI22_island)	C++14	15 / 100	338 ms	28300 KiB

island

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

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