oj.uz

Submission #705039

# Submission time Handle Problem Language Result Execution time Memory
705039 2023-03-03T08:59:39 Z Nursik Tenis (COI19_tenis) C++14
39 / 100
 500 ms 9432 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 = 2e5 + 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 0 ms 340 KB Output is correct
6 Correct 1 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 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 2 ms 372 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 4 ms 468 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 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 2 ms 372 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 4 ms 468 KB Output is correct
12 Correct 4 ms 340 KB Output is correct
13 Execution timed out 693 ms 5800 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 7456 KB Output is correct
2 Correct 168 ms 9252 KB Output is correct
3 Correct 166 ms 9304 KB Output is correct
4 Correct 166 ms 9392 KB Output is correct
5 Correct 174 ms 9252 KB Output is correct
6 Correct 161 ms 9344 KB Output is correct
7 Correct 191 ms 9348 KB Output is correct
8 Correct 164 ms 9288 KB Output is correct
9 Correct 186 ms 9324 KB Output is correct
10 Correct 193 ms 9364 KB Output is correct
11 Correct 176 ms 9432 KB Output is correct
12 Correct 171 ms 9288 KB Output is correct
13 Correct 174 ms 9372 KB Output is correct
14 Correct 173 ms 9344 KB Output is correct
15 Correct 165 ms 9340 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 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 2 ms 372 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 4 ms 468 KB Output is correct
12 Correct 4 ms 340 KB Output is correct
13 Execution timed out 693 ms 5800 KB Time limit exceeded
14 Halted 0 ms 0 KB -