Submission #705272

#	Time	Username	Problem	Language	Result	Execution time	Memory
705272		Nursik	Tenis (COI19_tenis)	C++14	100 / 100	150 ms	7804 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 + 1, maxm = 3e5 + 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];
struct seg_tree{
    int t[maxn * 4], mv[maxn * 4];
    void build(int v = 1, int tl = 1, int tr = n){
        mv[v] = 0;
        if (tl == tr){
            t[v] = tl;
            return;
        }
        int tm = (tl + tr) / 2;
        build(v + v, tl, tm);
        build(v + v + 1, tm + 1, tr);
        t[v] = min(t[v + v], t[v + v + 1]);
    }
    void push(int v, int l, int r){
        if (mv[v]){
            t[v] += mv[v];
            if (l != r){
                mv[v + v] += mv[v];
                mv[v + v + 1] += mv[v];
            }
            mv[v] = 0;
        }
    }
    void updlr(int l, int r, int val, int v = 1, int tl = 1, int tr = n){
        push(v, tl, tr);
      //  cout << v << " " << tl << " " << tr << '\n';
        if (l <= tl && tr <= r){
            mv[v] += val;
            push(v, tl, tr);
            return;
        }
        if (l > tr || r < tl)
            return;
        int tm = (tl + tr) / 2;
        updlr(l, r, val, v + v, tl, tm);
        updlr(l, r, val, v + v + 1, tm + 1, tr);
        t[v] = min(t[v + v], t[v + v + 1]);
    }
    int get(int v = 1, int tl = 1, int tr = n){
        push(v, tl, tr);
        if (tl == tr)
            return tl;
        int tm = (tl + tr) / 2;
        push(v + v, tl, tm);
        push(v + v + 1, tm + 1, tr);
        if (t[v + v] == 0)
            return get(v + v, tl, tm);
        else
            return get(v + v + 1, tm + 1, tr);
    }
} rt;
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.build();
    for (int i = 1; i <= n; ++i){
        int x = max({pos[1][i], pos[2][i], pos[3][i]});
     //   cout << x << " " << n << '\n';
        rt.updlr(x, n, -1);
    }
   // exit(0);
    for (int i = 1; i <= q; ++i){
        int type;
        cin >> type;
        if (type == 1){
            int x;
            cin >> x;
            int y = rt.get();
            int z = max({pos[1][x], pos[2][x], pos[3][x]});
            if (z <= y){
                cout << "DA\n";
            }
            else{
                cout << "NE\n";
            }
        }
        else{
            int p, x, y, z;
            cin >> p >> x >> y;
            z = max({pos[1][x], pos[2][x], pos[3][x]});
            rt.updlr(z, n, 1);
            z = max({pos[1][y], pos[2][y], pos[3][y]});
            rt.updlr(z, n, 1);
            swap(pos[p][x], pos[p][y]);
            z = max({pos[1][x], pos[2][x], pos[3][x]});
            rt.updlr(z, n, -1);
            z = max({pos[1][y], pos[2][y], pos[3][y]});
            rt.updlr(z, n, -1);
        }
    }
}
/*
*/

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 49 / 49