oj.uz

Submission #1113552

# Submission time Handle Problem Language Result Execution time Memory
1113552 2024-11-16T17:50:47 Z PagodePaiva Alternating Current (BOI18_alternating) C++17
19 / 100
 115 ms 17892 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];

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.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12880 KB Output is correct
2 Correct 9 ms 12880 KB Output is correct
3 Incorrect 9 ms 12880 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12880 KB Output is correct
2 Correct 9 ms 12880 KB Output is correct
3 Incorrect 9 ms 12880 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12880 KB Output is correct
2 Correct 9 ms 12880 KB Output is correct
3 Incorrect 9 ms 12880 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 17604 KB Output is correct
2 Correct 10 ms 15184 KB Output is correct
3 Correct 46 ms 16476 KB Output is correct
4 Correct 47 ms 16328 KB Output is correct
5 Correct 91 ms 17768 KB Output is correct
6 Correct 92 ms 17852 KB Output is correct
7 Correct 88 ms 17596 KB Output is correct
8 Correct 15 ms 14928 KB Output is correct
9 Correct 12 ms 14928 KB Output is correct
10 Correct 101 ms 17880 KB Output is correct
11 Correct 78 ms 17216 KB Output is correct
12 Correct 89 ms 17596 KB Output is correct
13 Correct 11 ms 14928 KB Output is correct
14 Correct 10 ms 14928 KB Output is correct
15 Correct 90 ms 17892 KB Output is correct
16 Correct 59 ms 16352 KB Output is correct
17 Correct 115 ms 17852 KB Output is correct
18 Correct 82 ms 15804 KB Output is correct
19 Correct 17 ms 15184 KB Output is correct
20 Correct 87 ms 16892 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12880 KB Output is correct
2 Correct 9 ms 12880 KB Output is correct
3 Incorrect 9 ms 12880 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -