Submission #654449

#	Time	Username	Problem	Language	Result	Execution time	Memory
654449		atigun	Stranded Far From Home (BOI22_island)	C++14	0 / 100	1092 ms	21412 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, -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];
  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: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35