oj.uz

Submission #167303

# Submission time Handle Problem Language Result Execution time Memory
167303 2019-12-07T09:01:30 Z egekabas Tenis (COI19_tenis) C++14
30 / 100
 500 ms 12664 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ull, ull>    pull;
typedef pair<ll, ll>  pll;
typedef pair<ld, ld>  pld;
struct player{
    int a, b, c;
};
player merge(player x, player y){
    return {min(x.a, y.a), min(x.b, y.b), min(x.b, y.b)};
}
int n, q;
player ar[100009];
player seg1[400009];
player seg2[400009];
player seg3[400009];
void upd(int v, int tl, int tr, int idx, player val, player seg[]){
    if(idx > tr || idx < tl)
        return;
    if(tl == idx && tr == idx){
        seg[v] = val;
        return;
    }
    else{
        int tm = (tl+tr)/2;
        upd(2*v, tl, tm, idx, val ,seg);
        upd(2*v+1, tm+1, tr, idx, val ,seg);
        seg[v] = merge(seg[2*v], seg[2*v+1]);
    }
}
player get(int v, int tl, int tr, int l, int r, player seg[]){
    if(l > tr || r < tl)
        return {(int)1e9, (int)1e9, (int)1e9};
    if(l <= tl && tr <= r){
        return seg[v];
    }
    else{
        int tm = (tl+tr)/2;
        return merge(get(2*v, tl, tm, l, r ,seg), get(2*v+1, tm+1, tr, l, r ,seg));
    }
}
player newopt(player a){
    player ret = merge(get(1, 0, n-1, a.a, n-1, seg1), get(1, 0, n-1, a.b, n-1, seg2));
    ret = merge(ret, get(1, 0, n-1, a.c, n-1, seg3));
    return ret;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n >> q;
    int t1;
    for(int i = 0; i < n; ++i){
        cin >> t1;
        ar[t1].a = i;
    }
    for(int i = 0; i < n; ++i){
        cin >> t1;
        ar[t1].b = i;
    }
    for(int i = 0; i < n; ++i){
        cin >> t1;
        ar[t1].c = i;
    }
    for(int i = 1; i <= n; ++i){
        upd(1, 0, n-1, ar[i].a, ar[i], seg1);
        upd(1, 0, n-1, ar[i].b, ar[i], seg2);
        upd(1, 0, n-1, ar[i].c, ar[i], seg3);
    }
    while(q--){
        int t;
        cin >> t;
        if(t == 1){
            int x;
            cin >> x;
            player cur = ar[x];
            for(int i = 0; i < n-1; ++i){
                player newcur = newopt(cur);
                if(cur.a == newcur.a && cur.b == newcur.b && cur.c == newcur.c)
                    break;
                cur = newcur;
            }
            if(cur.a == 0 && cur.b == 0 && cur.c == 0)
                cout << "DA\n";
            else
                cout << "NE\n";
        }
        else{
            int x, y, z;
            cin >> x >> y >> z;
            player &p1 = ar[y];
            player &p2 = ar[z];
            
            if(x == 1){
                swap(p1.a, p2.a);
            }
            if(x == 2){
                swap(p1.b, p2.b);
            }
            if(x == 3){
                swap(p1.c, p2.c);
            }
            upd(1, 0, n-1, p1.a, p1, seg1);
            upd(1, 0, n-1, p1.b, p1, seg2);
            upd(1, 0, n-1, p1.c, p1, seg3);

            upd(1, 0, n-1, p2.a, p2, seg1);
            upd(1, 0, n-1, p2.b, p2, seg2);
            upd(1, 0, n-1, p2.c, p2, seg3);
        }
    }
}

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 420 KB Output is correct
2 Correct 0 ms 376 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 189 ms 12508 KB Output is correct
14 Correct 174 ms 12528 KB Output is correct
15 Correct 180 ms 12536 KB Output is correct
16 Correct 185 ms 12552 KB Output is correct
17 Correct 196 ms 12536 KB Output is correct
18 Correct 181 ms 12536 KB Output is correct
19 Correct 183 ms 12508 KB Output is correct
20 Correct 185 ms 12536 KB Output is correct
21 Correct 193 ms 12536 KB Output is correct
22 Correct 193 ms 12536 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1059 ms 12664 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 420 KB Output is correct
2 Correct 0 ms 376 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 189 ms 12508 KB Output is correct
14 Correct 174 ms 12528 KB Output is correct
15 Correct 180 ms 12536 KB Output is correct
16 Correct 185 ms 12552 KB Output is correct
17 Correct 196 ms 12536 KB Output is correct
18 Correct 181 ms 12536 KB Output is correct
19 Correct 183 ms 12508 KB Output is correct
20 Correct 185 ms 12536 KB Output is correct
21 Correct 193 ms 12536 KB Output is correct
22 Correct 193 ms 12536 KB Output is correct
23 Execution timed out 1059 ms 12664 KB Time limit exceeded
24 Halted 0 ms 0 KB -