oj.uz

Submission #160737

# Submission time Handle Problem Language Result Execution time Memory
160737 2019-10-29T15:38:40 Z alexandra_udristoiu Tenis (COI19_tenis) C++14
30 / 100
 500 ms 9800 KB 
#include<iostream>
#define DIM 100005
#define f first
#define s second
using namespace std;
int n, q, i, ii, x, y, t, sol;
int poz[3][DIM], v[3][DIM];
pair<long long, long long> aint[4 * DIM];
void update(int nod, int st, int dr, int p){
    if(st == dr){
        aint[nod].f = aint[nod].s = 2 * st - poz[0][ v[1][p] ] - poz[0][ v[2][p] ];
    }
    else{
        int mid = (st + dr) / 2;
        if(p <= mid){
            update(2 * nod, st, mid, p);
        }
        else{
            update(2 * nod + 1, mid + 1, dr, p);
        }
        aint[nod].s = aint[2 * nod].s + aint[2 * nod + 1].s;
        aint[nod].f = max(aint[2 * nod].f, aint[2 * nod + 1].f + aint[2 * nod].s);
    }
}
int query(int nod, int st, int dr){
    if(st == dr){
        return st;
    }
    else{
        int mid = (st + dr) / 2;
        if(aint[nod].f == aint[2 * nod].f){
            return query(2 * nod, st, mid);
        }
        else{
            return query(2 * nod + 1, mid + 1, dr);
        }
    }
}
int main(){
    cin>> n >> q;
    for(ii = 0; ii < 3; ii++){
        for(i = 1; i <= n; i++){
            cin>> v[ii][i];
            poz[ii][ v[ii][i] ] = i;
        }
    }
    for(i = 1; i <= n; i++){
        update(1, 1, n, i);
    }
    sol = query(1, 1, n);
    for(; q; q--){
        cin>> t;
        if(t == 1){
            cin>> x;
            if(poz[0][x] <= sol){
                cout<<"DA\n";
            }
            else{
                cout<<"NE\n";
            }
        }
        else{
            cin>> ii >> x >> y;
            ii--;
            swap(poz[ii][x], poz[ii][y]);
            v[ii][ poz[ii][x] ] = x;
            v[ii][ poz[ii][y] ] = y;
            update(1, 1, n, poz[1][x]);
            update(1, 1, n, poz[1][y]);
            update(1, 1, n, poz[2][x]);
            update(1, 1, n, poz[2][y]);
            sol = query(1, 1, n);
        }
    }
}

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 9 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 174 ms 8544 KB Output is correct
14 Correct 179 ms 8540 KB Output is correct
15 Correct 174 ms 8596 KB Output is correct
16 Correct 177 ms 8700 KB Output is correct
17 Correct 175 ms 8536 KB Output is correct
18 Correct 182 ms 8656 KB Output is correct
19 Correct 170 ms 8440 KB Output is correct
20 Correct 177 ms 8468 KB Output is correct
21 Correct 175 ms 8568 KB Output is correct
22 Correct 174 ms 8676 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 521 ms 9800 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 9 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 174 ms 8544 KB Output is correct
14 Correct 179 ms 8540 KB Output is correct
15 Correct 174 ms 8596 KB Output is correct
16 Correct 177 ms 8700 KB Output is correct
17 Correct 175 ms 8536 KB Output is correct
18 Correct 182 ms 8656 KB Output is correct
19 Correct 170 ms 8440 KB Output is correct
20 Correct 177 ms 8468 KB Output is correct
21 Correct 175 ms 8568 KB Output is correct
22 Correct 174 ms 8676 KB Output is correct
23 Execution timed out 521 ms 9800 KB Time limit exceeded
24 Halted 0 ms 0 KB -