Submission #1113552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113552		PagodePaiva	Alternating Current (BOI18_alternating)	C++17	19 / 100	115 ms	17892 KiB

alternating

#include<bits/stdc++.h>
#define fr first
#define sc second

using namespace std;

const int N = 200010;

struct Segtree{
  pair <int, int> tree[4*N]; int lazy[4*N];
  pair <int, int> join(pair <int, int> a, pair <int, int> b){
    if(a.fr < b.fr) return a;
    else if(b.fr < a.fr) return b;
    if(a.sc < b.sc) return a;
    return b;
  }
  void unlazy(int node, int l, int r){
    if(lazy[node] == 0) return;
    tree[node].first = lazy[node];
    tree[node].second = l;
    if(l != r){
      lazy[2*node] = lazy[node];
      lazy[2*node+1] = lazy[node];
    }
    lazy[node] = 0;
  }
  void build(int node, int l,int r){
    lazy[node] = 0;
    if(l == r){
      tree[node] = {0, l};
      return;
    }
    int mid = (l+r)/2;
    build(2*node, l, mid);
    build(2*node+1, mid+1, r);
    tree[node] = join(tree[2*node], tree[2*node+1]);
    return;
  }
  void update(int node, int l, int r, int tl, int tr, int val){
    unlazy(node, tl, tr);
    if(l > tr or tl > r) return;
    if(l <= tl and tr <= r){
      lazy[node] = val;
      unlazy(node, tl, tr);
      return;
    }
    int mid = (tl+tr)/2;
    update(2*node, l, r, tl, mid, val);
    update(2*node+1, l, r, mid+1,tr, val);
    tree[node] = join(tree[2*node], tree[2*node+1]);
    return;
  }
  pair <int, int> query(int node, int l, int r, int tl, int tr){
    unlazy(node, tl, tr);
    if(l > tr or tl > r) return {2, 0};
    if(l <= tl and tr <= r) return tree[node];
    int mid = (tl+tr)/2;
    return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
  }
} seg[2];

vector <array <int, 3>> intervalos;
int res[N];

int main(){
  int n, m;
  cin >> n >> m;
  for(int i = 1;i <= m;i++){
    int a, b;
    cin >> a >> b;
    intervalos.push_back({a, -b, i-1});
  }
  sort(intervalos.begin(), intervalos.end());
  for(int i = 0;i < m;i++){
    intervalos[i][1] *= -1;
  }
  seg[0].build(1, 1, n);
  seg[1].build(1, 1, n);
  for(int i = 0;i < m;i++){
    auto [l, r, _] = intervalos[i];
    pair <int, int> a = seg[0].query(1, l, r, 1, n);
    pair <int, int> b = seg[1].query(1, l, r, 1, n);
    if(a.fr == 1 and b.fr == 1){
      res[_] = 0;
      continue;
    }
    else if(a.fr == 1 and b.fr == 0){
      res[_] = 1;
      seg[1].update(1, l, r, 1, n, 1);
    }
    else if(a.fr == 0 and b.fr == 1){
      res[_] = 0;
      seg[0].update(1, l, r, 1, n, 1);
    }
    else{
      if(a.sc < b.sc){
        res[_] = 0;
        seg[0].update(1, l, r, 1, n, 1);
      }
      else{
        res[_] = 1;
        seg[1].update(1, l, r, 1, n, 1);
      }
    }
  }
  if(seg[0].query(1, 1, n, 1, n).fr != 1 or seg[1].query(1, 1, n, 1, n).sc != 1){
    cout << "impossible\n";
    return 0;
  }
  for(int i = 0;i < m;i++){
    cout << res[i];
  }
  cout << '\n';
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 19 / 19
• Subtask 5: 0 / 26