oj.uz

Submission #1113566

# Submission time Handle Problem Language Result Execution time Memory
1113566 2024-11-16T18:18:05 Z PagodePaiva Alternating Current (BOI18_alternating) C++17
19 / 100
 190 ms 37316 KB 
#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);
    }
    for(int i = 0;i < intervalos.size();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';
  }
  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

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:172: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]
  172 |     for(int i = 0;i < intervalos.size();i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~
alternating.cpp:220: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]
  220 |     for(int i = 0;i < intervalos.size();i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24912 KB Output is correct
2 Correct 4 ms 23632 KB Output is correct
3 Correct 5 ms 23632 KB Output is correct
4 Correct 6 ms 23632 KB Output is correct
5 Correct 4 ms 25084 KB Output is correct
6 Correct 4 ms 24912 KB Output is correct
7 Correct 3 ms 24912 KB Output is correct
8 Correct 3 ms 24912 KB Output is correct
9 Correct 3 ms 24912 KB Output is correct
10 Correct 6 ms 23632 KB Output is correct
11 Incorrect 5 ms 23756 KB no wires in direction 1 between segments 2 and 2
12 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24912 KB Output is correct
2 Correct 4 ms 23632 KB Output is correct
3 Correct 5 ms 23632 KB Output is correct
4 Correct 6 ms 23632 KB Output is correct
5 Correct 4 ms 25084 KB Output is correct
6 Correct 4 ms 24912 KB Output is correct
7 Correct 3 ms 24912 KB Output is correct
8 Correct 3 ms 24912 KB Output is correct
9 Correct 3 ms 24912 KB Output is correct
10 Correct 6 ms 23632 KB Output is correct
11 Incorrect 5 ms 23756 KB no wires in direction 1 between segments 2 and 2
12 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24912 KB Output is correct
2 Correct 4 ms 23632 KB Output is correct
3 Correct 5 ms 23632 KB Output is correct
4 Correct 6 ms 23632 KB Output is correct
5 Correct 4 ms 25084 KB Output is correct
6 Correct 4 ms 24912 KB Output is correct
7 Correct 3 ms 24912 KB Output is correct
8 Correct 3 ms 24912 KB Output is correct
9 Correct 3 ms 24912 KB Output is correct
10 Correct 6 ms 23632 KB Output is correct
11 Incorrect 5 ms 23756 KB no wires in direction 1 between segments 2 and 2
12 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 33980 KB Output is correct
2 Correct 21 ms 33872 KB Output is correct
3 Correct 99 ms 31424 KB Output is correct
4 Correct 97 ms 31936 KB Output is correct
5 Correct 140 ms 34112 KB Output is correct
6 Correct 143 ms 33164 KB Output is correct
7 Correct 129 ms 34508 KB Output is correct
8 Correct 30 ms 29776 KB Output is correct
9 Correct 27 ms 29520 KB Output is correct
10 Correct 135 ms 37316 KB Output is correct
11 Correct 113 ms 32860 KB Output is correct
12 Correct 115 ms 37064 KB Output is correct
13 Correct 21 ms 30288 KB Output is correct
14 Correct 19 ms 31824 KB Output is correct
15 Correct 128 ms 33212 KB Output is correct
16 Correct 97 ms 32704 KB Output is correct
17 Correct 190 ms 34492 KB Output is correct
18 Correct 120 ms 29428 KB Output is correct
19 Correct 36 ms 30800 KB Output is correct
20 Correct 123 ms 31208 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24912 KB Output is correct
2 Correct 4 ms 23632 KB Output is correct
3 Correct 5 ms 23632 KB Output is correct
4 Correct 6 ms 23632 KB Output is correct
5 Correct 4 ms 25084 KB Output is correct
6 Correct 4 ms 24912 KB Output is correct
7 Correct 3 ms 24912 KB Output is correct
8 Correct 3 ms 24912 KB Output is correct
9 Correct 3 ms 24912 KB Output is correct
10 Correct 6 ms 23632 KB Output is correct
11 Incorrect 5 ms 23756 KB no wires in direction 1 between segments 2 and 2
12 Halted 0 ms 0 KB -