제출 #705040

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
705040		Nursik	Tenis (COI19_tenis)	C++14	39 / 100	695 ms	6936 KiB

tenis

#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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 0 / 12
• Subtask 4: 21 / 21
• Subtask 5: 0 / 49