Submission #274934

#	Time	Username	Problem	Language	Result	Execution time	Memory
274934		caoash	Tenis (COI19_tenis)	C++14	30 / 100	547 ms	7032 KiB

tenis

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

using ll = long long;

using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair

const int MX = 100005;

int a[3][MX];

template<class T, int SZ> struct LazySeg{
  T tree[4 * SZ], lazy[4 * SZ];

  T merge(T a, T b){
    return min(a, b);
  }

  void prop(int v, int l, int r){
    if (lazy[v] != 0) {
      tree[v] += lazy[v];
      if (l != r) {
        lazy[2 * v + 1] += lazy[v];
        lazy[2 * v + 2] += lazy[v];
      }
      lazy[v] = 0;
    }
  }

  void update(int v, int l, int r, int ql, int qr, int x) {
    prop(v, l, r); 
    if (r < ql || l > qr) {
      return;
    }
    if (l >= ql && r <= qr) {
      tree[v] += x;
      if (l != r) {
        lazy[2 * v + 1] += x;
        lazy[2 * v + 2] += x;
      }
      return;
    }
    int m = (l + r) / 2;
    update(2 * v + 1, l, m, ql, qr, x);
    update(2 * v + 2, m + 1, r, ql, qr, x);
    tree[v] = merge(tree[2 * v + 1], tree[2 * v +2]);
  }

  T query(int v, int l, int r, int ql, int qr) {
    prop(v, l, r); 
    if (l > qr || r < ql) {
      return INT_MAX;
    }
    if (l >= ql && r <= qr) {
      return tree[v];
    } else {
      int m = (l + r) / 2;
      T a = query(2 * v + 1, l, m, ql, qr);
      T b = query(2 * v + 2, m + 1, r, ql, qr);
      return merge(a,b);
    }
  }

};

LazySeg<int, MX> orz; int mi[MX]; int pos[3][MX];

int main(){
    int n, q; cin >> n >> q;
    for (int i = 0; i < 3; i++) for (int j = 0; j < n; j++) {
        cin >> a[i][j];
        mi[a[i][j]] = max(mi[a[i][j]], j);
        pos[i][a[i][j]] = j;
    }
    for (int i = 0; i < n; i++) {
        orz.update(0, 0, n - 1, i, i, i + 1);
        // cout << "setting " << i << " " << i + 1 << '\n';
    }
    for (int i = 1; i <= n; i++) {
        orz.update(0, 0, n - 1, mi[i], n - 1, -1);
        // cout << "setting " << " " << i << " " << mi[i] << " " << n - 1 << " " << -1 << '\n';
    }
    int cbest = n;
    auto relax = [&] () {
        int lo = 0; int hi = n - 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (orz.query(0, 0, n - 1, 0, mid) == 0) {
                cbest = mid;
                hi = mid - 1;
            }
            else {
                lo = mid + 1;
            }
        }
    };
    relax();
    auto swp = [&] (int p, int i, int j) {
        swap(pos[p][i], pos[p][j]);
        mi[i] = max({pos[0][i], pos[1][i], pos[2][i]});
        mi[j] = max({pos[0][j], pos[1][j], pos[2][j]});
    };
    for (int i = 0; i < q; i++) {
        int qt; cin >> qt;
        if (qt == 1) {
            int x; cin >> x;
            if (mi[x] <= cbest) {
                cout << "DA" << '\n';
            }
            else {
                cout << "NE" << '\n';
            }
        }
        else {
            int p, x, y; cin >> p >> x >> y;
            p--;
            orz.update(0, 0, n - 1, mi[x], n - 1, 1);
            orz.update(0, 0, n - 1, mi[y], n - 1, 1);
            swp(p, x, y);
            orz.update(0, 0, n - 1, mi[x], n - 1, -1);
            orz.update(0, 0, n - 1, mi[y], n - 1, -1);
            relax();
        }
    }
}

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