Submission #234225

#	Time	Username	Problem	Language	Result	Execution time	Memory
234225		Vimmer	Tenis (COI19_tenis)	C++14	39 / 100	751 ms	7832 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], mn_pos[N], n, q, pos[3][N];

bool win[N], t[3][N * 4];

void bld(int j, int v, int tl, int tr)
{
    t[j][v] = 0;

    if (tl == tr)
    {
        if (mn_pos[a[j][tl]] == 1) t[j][v] = 1;

        return;
    }

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

    bld(j, v + v, tl, md);

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

    t[j][v] = (t[j][v + v] | t[j][v + v + 1]);
}

bool get(int j, int v, int tl, int tr, int l, int r)
{
    if (tr < l || r < tl || tl > tr || l > r) return 0;

    if (l <= tl && tr <= r) return t[j][v];

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

    return (get(j, v + v, tl, md, l, r) | get(j, v + v + 1, md + 1, tr, l, r));
}

void upd(int j, int v, int tl, int tr, int pos)
{
    if (tl == tr) t[j][v] = 1;
    else
    {
        int md = (tl + tr) >> 1;

        if (pos <= md) upd(j, v + v, tl, md, pos);
          else upd(j, v + v + 1, md + 1, tr, pos);

        t[j][v] = t[j][v + v] | t[j][v + v + 1];
    }
}

void build()
{
    for (int i = 1; i <= n; i++) mn_pos[i] = 1e9;

    for (int j = 0; j < 3; j++)
        for (int i = 1; i <= n; i++)
        {
            mn_pos[a[j][i]] = min(mn_pos[a[j][i]], i);

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

    for (int j = 0; j < 3; j++) bld(j, 1, 1, n);

    vector <pair <int, int> > g; g.clear();

    for (int i = 1; i <= n; i++) g.pb({mn_pos[i], i});

    sort(g.begin(), g.end());

    for (auto it : g)
    {
        win[it.S] = 0;

        for (int j = 0; j < 3; j++) win[it.S] |= get(j, 1, 1, n, pos[j][it.S], n);

        if (win[it.S])
            for (int j = 0; j < 3; j++) upd(j, 1, 1, n, pos[j][it.S]);
    }
}
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];

    build();

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

        cin >> tp;

        if (tp == 2)
        {
            int j, l, r;

            cin >> j >> l >> r;

            j--;

            a[j][pos[j][l]] = r;

            a[j][pos[j][r]] = l;

            build();

            continue;
        }

        cin >> p;

        if (win[p]) cout << "DA" << '\n';
          else cout << "NE" << '\n';
    }
}

Compilation message (stderr)

tenis.cpp: In function 'int main()':
tenis.cpp:125:20: warning: unused variable 'l' [-Wunused-variable]
         int tp, p, l, r;
                    ^
tenis.cpp:125:23: warning: unused variable 'r' [-Wunused-variable]
         int tp, p, l, r;
                       ^

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