Submission #1113570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113570		PagodePaiva	Alternating Current (BOI18_alternating)	C++17	32 / 100	199 ms	33712 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];

struct Segtree2{
  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;
    if(a.fr > b.fr) return b;
    return a;
  }
  void unlazy(int node, int l, int r){
    tree[node].first += lazy[node];
    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 {1e9, 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));
  }
} segint;

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;
  }
  segint.build(1, 1, n);
  for(auto [a, b, i] : intervalos){
    if(b > a){
      segint.update(1, a, b-1, 1, n, 1);
    }
    else if(b < a){
      segint.update(1, a, n, 1, n, 1);
      if(b == 1) continue;
      segint.update(1, 1, b-1, 1, n, 1);
    }
  }
  pair <int, int> t = segint.query(1, 1, n, 1, n);
  if(t.fr <= 1){
    seg[0].build(1, 1, n);
    seg[1].build(1, 1, n);
    int st = t.sc+1;
    if(st > n) st = 1;
    map <int, int> aux;
    for(int i = 0;i < n;i++){
      int d = st+i;
      if(d > n) d %= n;
      aux[d] = i+1;
    }
    array <int, 3> amigao = {-1, -1, -1};
    vector <array <int, 3>> aaa;
    for(int i = 0;i < m;i++){
      intervalos[i][0] = aux[intervalos[i][0]];
      intervalos[i][1] = aux[intervalos[i][1]];
      if(intervalos[i][1] < intervalos[i][0]){
        amigao = intervalos[i];
      }
      else{
        aaa.push_back({intervalos[i][0], -intervalos[i][1], intervalos[i][2]});
      }
    }
    intervalos = aaa;
    sort(intervalos.begin(), intervalos.end());
    for(int i = 0;i < intervalos.size();i++){
      intervalos[i][1] *= -1;
    }
    if(amigao[0] != -1){
      res[amigao[2]] = 0;
      seg[0].update(1, amigao[0], n, 1, n, 1);
      seg[0].update(1, 1, amigao[1], 1, n, 1);
      //cout << amigao[0] << ' ' << amigao[1] << '\n';
    }
    for(int i = 0;i < intervalos.size();i++){
      auto [l, r, _] = intervalos[i];
      //cout << l << ' ' << r << '\n';
      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).fr != 1){
      cout << "impossible\n";
      return 0;
    }
    for(int i = 0;i < m;i++){
      cout << res[i];
    }
    cout << '\n';
    return 0;
  }
  else{
    for(int i = 0;i < m;i++){
      if(intervalos[i][1] < intervalos[i][0]) intervalos[i][1] += n;
      intervalos[i][1] *= -1;
    }
    sort(intervalos.begin(), intervalos.end());
    for(int i = 0;i < m;i++){
      intervalos[i][1] *= -1;
      if(intervalos[i][1] > n) intervalos[i][1] -= n;
    }
    seg[0].build(1, 1, n);
    seg[1].build(1, 1, n);
    for(int i = 0;i < intervalos.size();i++){
      auto [l, r, _] = intervalos[i];
      if(l < r){
        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);
          }
        }
      }
      else{
        pair <int, int> a = seg[0].query(1, l, n, 1, n);
        pair <int, int> b = seg[1].query(1, l, n, 1, n);
        if(a.fr == 1 and b.fr == 1){
          a = seg[0].query(1, 1, r, 1, n);
          b = seg[1].query(1, 1, 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, n, 1, n, 1);
            seg[1].update(1, 1, r, 1, n, 1);
          }
          else if(a.fr == 0 and b.fr == 1){
            res[_] = 0;
            seg[0].update(1, l, n, 1, n, 1);
            seg[0].update(1, 1, r, 1, n, 1);
          }
          else{
            if(a.sc < b.sc){
              res[_] = 0;
              seg[0].update(1, l, n, 1, n, 1);
              seg[0].update(1, 1, r, 1, n, 1);
            }
            else{
              res[_] = 1;
              seg[1].update(1, l, n, 1, n, 1);
              seg[1].update(1, 1, r, 1, n, 1);
            }
          }
          continue;
        }
        else if(a.fr == 1 and b.fr == 0){
          res[_] = 1;
          seg[1].update(1, l, n, 1, n, 1);
          seg[1].update(1, 1, r, 1, n, 1);
        }
        else if(a.fr == 0 and b.fr == 1){
          res[_] = 0;
          seg[0].update(1, l, n, 1, n, 1);
          seg[0].update(1, 1, r, 1, n, 1);
        }
        else{
          if(a.sc < b.sc){
            res[_] = 0;
            seg[0].update(1, l, n, 1, n, 1);
            seg[0].update(1, 1, r, 1, n, 1);
          }
          else{
            res[_] = 1;
            seg[1].update(1, l, n, 1, n, 1);
            seg[1].update(1, 1, r, 1, n, 1);
          }
        }
      }
    }
    for(int i = 0;i < m;i++){
      cout << res[i];
    }
    cout << '\n';
  }
}

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:164:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |     for(int i = 0;i < intervalos.size();i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~
alternating.cpp:173:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |     for(int i = 0;i < intervalos.size();i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~
alternating.cpp:223:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |     for(int i = 0;i < intervalos.size();i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~

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