oj.uz

Submission #705040

# Submission time Handle Problem Language Result Execution time Memory
705040 2023-03-03T09:02:59 Z Nursik Tenis (COI19_tenis) C++14
39 / 100
 500 ms 6936 KB 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <functional>
#include <complex>
#include <random>

using namespace std;
 
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
 
const ll maxn = 1e5 + 10, maxm = 20 + 1;
const ll mod = 1e9 + 7, cmod = 998244353, inf = 1e9, blcok = 400, p2 = 31;
const ld eps = 1e-9;


int n, q;
int a[5][maxn], pos[5][maxn];
int type[maxn], x[maxn], ap[maxn], bp[maxn], p[maxn];
struct seg_tree{
    int t[maxn * 4];
    void build(int v = 1, int tl = 1, int tr = n){
        if (tl == tr){
            t[v] = inf;
            return;
        }
        int tm = (tl + tr) / 2;
        build(v + v, tl, tm);
        build(v + v + 1, tm + 1, tr);
        t[v] = inf;
    }
    void upd(int pos, int val, int v = 1, int tl = 1, int tr = n){
        if (tl == tr){
            t[v] = min(t[v], val);
            return;
        }
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            upd(pos, val, v + v, tl, tm);
        else
            upd(pos, val, v + v + 1, tm + 1, tr);
        t[v] = min(t[v + v], t[v + v + 1]);
    }
    int get(int l, int r, int v = 1, int tl = 1, int tr = n){
        if (l <= tl && tr <= r)
            return t[v];
        if (l > tr || r < tl)
            return inf;
        int tm = (tl + tr) / 2;
        return min(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
    }
} rt[4];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    cin >> n >> q;
    for (int i = 1; i <= 3; ++i){
        for (int j = 1; j <= n; ++j){
            cin >> a[i][j];
            pos[i][a[i][j]] = j;
        }
        rt[i].build();
    }
    for (int i = 1; i <= q; ++i){
        cin >> type[i];
        if (type[i] == 1){
            cin >> x[i];
        }
        else{
            cin >> p[i] >> ap[i] >> bp[i];    
        }
    }
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= 3; ++j){
            int is = min(i, rt[j].get(i + 1, n));
            for (int k = 1; k <= 3; ++k){
                int pos1 = pos[k][a[j][i]];
                rt[k].upd(pos1, is);
            }
        }
    }
    for (int i = 1; i <= q; ++i){
        if (type[i] == 1){
            int ans = inf;
            for (int j = 1; j <= 3; ++j){
                ans = min(ans, rt[j].get(pos[j][x[i]], n));
            }
            if (ans == 1){
                cout << "DA\n";
            }
            else{
                cout << "NE\n";
            }
        }
        else{   
            int ps = pos[p[i]][ap[i]], ps2 = pos[p[i]][bp[i]];
            swap(a[p[i]][ps], a[p[i]][ps2]);
            swap(pos[p[i]][ap[i]], pos[p[i]][bp[i]]);
            for (int k = 1; k <= 3; ++k){
                rt[k].build();
            }
            for (int j = 1; j <= n; ++j){
                for (int k = 1; k <= 3; ++k){
                    int is = min(j, rt[k].get(j + 1, n));
                    for (int k2 = 1; k2 <= 3; ++k2){
                        int pos1 = pos[k2][a[k][j]];
                        rt[k2].upd(pos1, is);
                    }
                }
            }
        }
    }
}
/*
*/

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 4 ms 444 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 4 ms 340 KB Output is correct
12 Correct 4 ms 340 KB Output is correct
13 Execution timed out 695 ms 5808 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 6804 KB Output is correct
2 Correct 187 ms 6728 KB Output is correct
3 Correct 171 ms 6804 KB Output is correct
4 Correct 170 ms 6820 KB Output is correct
5 Correct 178 ms 6780 KB Output is correct
6 Correct 172 ms 6936 KB Output is correct
7 Correct 178 ms 6748 KB Output is correct
8 Correct 167 ms 6784 KB Output is correct
9 Correct 166 ms 6800 KB Output is correct
10 Correct 174 ms 6808 KB Output is correct
11 Correct 169 ms 6800 KB Output is correct
12 Correct 165 ms 6820 KB Output is correct
13 Correct 184 ms 6816 KB Output is correct
14 Correct 165 ms 6764 KB Output is correct
15 Correct 167 ms 6800 KB Output is correct

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 4 ms 444 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 4 ms 340 KB Output is correct
12 Correct 4 ms 340 KB Output is correct
13 Execution timed out 695 ms 5808 KB Time limit exceeded
14 Halted 0 ms 0 KB -