Submission #171671

#	Time	Username	Problem	Language	Result	Execution time	Memory
171671		Milki	Tenis (COI19_tenis)	C++14	100 / 100	188 ms	9364 KiB

tenis

#include<bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " " <<

typedef long long ll;
typedef pair<int, int> point;

const int mod = 1e9 + 7;

int add(int x, int y) {x += y; if(x >= mod) return x - mod; return x;}
int sub(int x, int y) {x -= y; if(x < 0) return x + mod; return x;}
int mul(int x, int y) {return (ll) x * y % mod;}

const int off = 1 << 17, MAXN = 1e5 + 5;

struct Node{
  int mn, pos, prop;
  Node(){}
  Node(int mn, int pos, int prop) : mn(mn), pos(pos), prop(prop) {}
};

Node merge(Node &A, Node &B){
  Node ret;
  if(A.mn <= B.mn)
    return Node(A.mn, A.pos, 0);
  else
    return Node(B.mn, B.pos, 0);
}

const int inf = 1e9;

struct Tournament{
  Node t[2 * off];

  void prop(int x){
    t[x].mn += t[x].prop;
    if(x < off){
      t[x * 2].prop += t[x].prop;
      t[x * 2 + 1].prop += t[x].prop;
    }
    t[x].prop = 0;
  }
  void update(int x, int lo, int hi, int a, int b, int val){
    prop(x);
    if(lo >= b || hi <= a) return;
    if(lo >= a && hi <= b) { t[x].prop += val; prop(x); return; }

    int mid = (lo + hi) >> 1;
    update(x * 2, lo, mid, a, b, val);
    update(x * 2 + 1, mid, hi, a, b, val);
    t[x] = merge(t[x * 2], t[x * 2 + 1]);
  }
  void init(){
    t[off] = Node(inf, inf, 0);
    for(int x = off + 1; x < 2 * off; ++x)
      t[x] = Node(x - off, x - off, 0);
    for(int x = off - 1; x >= 0; --x)
      t[x] = merge(t[x * 2], t[x * 2 + 1]);
  }
  int query(){
    prop(1);
    return t[1].pos;
  }
} T;

int n, q, p[3][MAXN], in[3][MAXN], mx[MAXN];

void refresh(int x){
  mx[x] = max( max(p[0][x], p[1][x]), p[2][x] );
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  cin >> n >> q;

  T.init();
  for(int i = 0; i < 3; ++i)
    for(int j = 0; j < n; ++j){
      cin >> in[i][j];
      in[i][j] --;
      p[i][ in[i][j] ] = j + 1;
    }
  for(int i = 0; i < n; ++i){
    refresh(i);
    T.update(1, 0, off, mx[i], off, -1);
  }

  for(int i = 0; i < q; ++i){
    int tip; cin >> tip;
    if(tip == 1){
      int x; cin >> x; x --;
      if(mx[x] <= T.query())
        cout << "DA\n";
      else
        cout << "NE\n";
    }
    else{
      int col, a, b; cin >> col >> a >> b;
      col --; a --; b --;

      T.update(1, 0, off, mx[a], off, 1);
      T.update(1, 0, off, mx[b], off, 1);

      swap(p[col][a], p[col][b]);
      refresh(a); refresh(b);

      T.update(1, 0, off, mx[a], off, -1);
      T.update(1, 0, off, mx[b], off, -1);
    }
  }
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 49 / 49