oj.uz

Submission #275232

# Submission time Handle Problem Language Result Execution time Memory
275232 2020-08-20T05:01:18 Z caoash Tenis (COI19_tenis) C++14
30 / 100
 500 ms 5472 KB 
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#pragma GCC optimize("unroll-loops")

#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 n; 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]);
  }

  void query(int v, int l, int r, int &best) {
    prop(v, l, r); 
    // cout << "walk on: " << v << " " << l << " " << r << '\n';
    if (tree[v] != 0) {
        best = min(best, n);
        return;
    }
    if (l == r) {
        best = min(best, l);
        return;
    } else {
      int m = (l + r) / 2;
      prop(2 * v + 1, l, m);
      prop(2 * v + 2, m + 1, r);
      tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
      if (tree[2 * v + 1] == 0) {
        query(2 * v + 1, l, m, best);
      }
      else {
        query(2 * v + 2, m + 1, r, best);
      }
      return;
    }
  }
};

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

int main(){
    int 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);
    }
    for (int i = 1; i <= n; i++) {
        orz.update(0, 0, n - 1, mi[i], n - 1, -1);
    }
    int cbest = n;
    auto relax = [&] () {
        cbest = n;
        orz.query(0, 0, n - 1, cbest);
    };
    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;
        // cout << "i, cbest: " << i << " " << cbest << '\n';
        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 416 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 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 416 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 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 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 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 416 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 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 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 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 234 ms 5160 KB Output is correct
14 Correct 241 ms 5112 KB Output is correct
15 Correct 227 ms 5112 KB Output is correct
16 Correct 227 ms 5112 KB Output is correct
17 Correct 234 ms 5240 KB Output is correct
18 Correct 241 ms 5112 KB Output is correct
19 Correct 226 ms 5088 KB Output is correct
20 Correct 239 ms 5240 KB Output is correct
21 Correct 236 ms 5112 KB Output is correct
22 Correct 239 ms 5112 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 544 ms 5472 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 416 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 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 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 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 234 ms 5160 KB Output is correct
14 Correct 241 ms 5112 KB Output is correct
15 Correct 227 ms 5112 KB Output is correct
16 Correct 227 ms 5112 KB Output is correct
17 Correct 234 ms 5240 KB Output is correct
18 Correct 241 ms 5112 KB Output is correct
19 Correct 226 ms 5088 KB Output is correct
20 Correct 239 ms 5240 KB Output is correct
21 Correct 236 ms 5112 KB Output is correct
22 Correct 239 ms 5112 KB Output is correct
23 Execution timed out 544 ms 5472 KB Time limit exceeded
24 Halted 0 ms 0 KB -