oj.uz

Submission #234225

# Submission time Handle Problem Language Result Execution time Memory
234225 2020-05-23T13:45:59 Z Vimmer Tenis (COI19_tenis) C++14
39 / 100
 500 ms 7832 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 7 ms 384 KB Output is correct
10 Correct 8 ms 384 KB Output is correct
11 Correct 7 ms 384 KB Output is correct
12 Correct 7 ms 512 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 7 ms 384 KB Output is correct
10 Correct 8 ms 384 KB Output is correct
11 Correct 7 ms 384 KB Output is correct
12 Correct 7 ms 512 KB Output is correct
13 Execution timed out 751 ms 7832 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 6900 KB Output is correct
2 Correct 126 ms 6900 KB Output is correct
3 Correct 123 ms 6900 KB Output is correct
4 Correct 129 ms 6900 KB Output is correct
5 Correct 117 ms 6900 KB Output is correct
6 Correct 115 ms 6900 KB Output is correct
7 Correct 128 ms 7004 KB Output is correct
8 Correct 123 ms 6936 KB Output is correct
9 Correct 130 ms 6900 KB Output is correct
10 Correct 117 ms 6900 KB Output is correct
11 Correct 135 ms 7040 KB Output is correct
12 Correct 128 ms 6900 KB Output is correct
13 Correct 127 ms 7020 KB Output is correct
14 Correct 121 ms 6900 KB Output is correct
15 Correct 114 ms 6900 KB Output is correct

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 7 ms 384 KB Output is correct
10 Correct 8 ms 384 KB Output is correct
11 Correct 7 ms 384 KB Output is correct
12 Correct 7 ms 512 KB Output is correct
13 Execution timed out 751 ms 7832 KB Time limit exceeded
14 Halted 0 ms 0 KB -