제출 #234261

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
234261		Vimmer	Tenis (COI19_tenis)	C++14	100 / 100	217 ms	9472 KiB

tenis

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")

#define sz(x) ll(x.size())
#define base 1000000
#define M ll(1e9+7)
#define N 100005
#define F first
#define S second
#define pb push_back
#define in insert
#define eb emplace_back
#define ed "\n"

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef short int si;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


int a[3][N], n, q, pos[3][N], psh[N * 4];

pair <int, int> t[N * 4];

void bld(int v, int tl, int tr)
{
    if (tl == tr) t[v] = {-tl, tl};

    else {

    int md = (tl + tr) >> 1;

    bld(v + v, tl, md);

    bld(v + v + 1, md + 1, tr);

    if (t[v + v].F > t[v + v + 1].F) t[v] = t[v + v + 1];
      else t[v] = t[v + v];
    }
}

void Push(int v)
{
    if (psh[v] == 0) return;

    t[v].F += psh[v];

    if (v + v + 1 < N * 4)
    {
        psh[v + v] += psh[v];

        psh[v + v + 1] += psh[v];
    }

    psh[v] = 0;
}

void upd(int v, int tl, int tr, int l, int r, int val)
{
    Push(v);

    if (tr < l || r < tl || tl > tr || l > r) return;

    if (l <= tl && tr <= r)
    {
        psh[v] += val;

        Push(v);

        return;
    }

    int md = (tl + tr) >> 1;

    upd(v + v, tl, md, l, r, val);

    upd(v + v + 1, md + 1, tr, l, r, val);

    if (t[v + v].F > t[v + v + 1].F) t[v] = t[v + v + 1];
      else t[v] = t[v + v];
}

void update(int v, int val) {upd(1, 1, n, min(min(pos[0][v], pos[1][v]), pos[2][v]), n, val);}

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> q;

    for (int j = 0; j < 3; j++)
        for (int i = 1; i <= n; i++)
        {
            cin >> a[j][i];

            pos[j][a[j][i]] = i;
        }

    bld(1, 1, n);

    for (int i = 1; i <= n; i++) update(i, 1);

    for (; q > 0; q--)
    {
        int tp, p, l, r;

        cin >> tp;

        if (tp == 2)
        {
            cin >> p >> l >> r;

            p--;

            update(l, -1);

            update(r, -1);

            swap(a[p][pos[p][l]], a[p][pos[p][r]]);

            swap(pos[p][l], pos[p][r]);

            update(l, 1);

            update(r, 1);

            continue;
        }

        cin >> p;

        if (t[1].S >= pos[0][p]) cout << "DA" << '\n';
          else cout << "NE" << '\n';
    }
}

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