oj.uz

Submission #274934

# Submission time Handle Problem Language Result Execution time Memory
274934 2020-08-20T01:35:03 Z caoash Tenis (COI19_tenis) C++14
30 / 100
 500 ms 7032 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 2 ms 416 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 2 ms 416 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 236 ms 6844 KB Output is correct
14 Correct 230 ms 6904 KB Output is correct
15 Correct 237 ms 6996 KB Output is correct
16 Correct 250 ms 6776 KB Output is correct
17 Correct 243 ms 6904 KB Output is correct
18 Correct 239 ms 7032 KB Output is correct
19 Correct 239 ms 6808 KB Output is correct
20 Correct 234 ms 6904 KB Output is correct
21 Correct 231 ms 6960 KB Output is correct
22 Correct 238 ms 6904 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 547 ms 5512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 2 ms 416 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 236 ms 6844 KB Output is correct
14 Correct 230 ms 6904 KB Output is correct
15 Correct 237 ms 6996 KB Output is correct
16 Correct 250 ms 6776 KB Output is correct
17 Correct 243 ms 6904 KB Output is correct
18 Correct 239 ms 7032 KB Output is correct
19 Correct 239 ms 6808 KB Output is correct
20 Correct 234 ms 6904 KB Output is correct
21 Correct 231 ms 6960 KB Output is correct
22 Correct 238 ms 6904 KB Output is correct
23 Execution timed out 547 ms 5512 KB Time limit exceeded
24 Halted 0 ms 0 KB -