oj.uz

Submission #167319

# Submission time Handle Problem Language Result Execution time Memory
167319 2019-12-07T11:03:38 Z egekabas Tenis (COI19_tenis) C++14
18 / 100
 500 ms 19192 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;
};
struct node{
    vector<int> v;
    int go;
};
int n, q;
player ar[100009];
node seg[400009];
int a[100009], b[100009], c[100009];
int getmaxi(player x){
    return max(max(x.a, x.b), (int)x.c);
}
int getmini(player x){
    return min(min(x.a, x.b), (int)x.c);
}
node merge(node a, node b){
    int it1 = 0;
    int it2 = lower_bound(b.v.begin(), b.v.end(), a.go)-b.v.begin();
    node ret;
    ret.go = max(a.go, b.go);
    while(it1 < a.v.size() || it2 < b.v.size()){
        if(it1 == a.v.size())
            ret.v.pb(b.v[it2++]);
        else if(it2 == b.v.size())
            ret.v.pb(a.v[it1++]);
        else if(a.v[it1] < b.v[it2])
            ret.v.pb(a.v[it1++]);
        else
            ret.v.pb(b.v[it2++]);        
    }
    return ret;
}
void update(int v, int tl, int tr, int idx){ 
    if(tr < idx || idx < tl)
        return;
    if(tl == idx && tr == idx){
        seg[v].v.clear();
        seg[v].go = max(max(getmaxi(ar[a[tl]]),
        getmaxi(ar[b[tl]])), getmaxi(ar[c[tl]]));
        if(seg[v].go <= tl)
            seg[v].v.pb(tl); 
    }
    else{
        int tm = (tl+tr)/2;
        update(2*v, tl, tm, idx);
        update(2*v+1, tm+1, tr, idx);
        seg[v] = merge(seg[2*v], seg[2*v+1]);
    }
}
/*
node get(int v, int tl, int tr, int l, int r){
    if(r < tl || l > tr)
        return {{}, 0};
    if(l <= tl && tr <= r)
        return seg[v];
    else{
        int tm = (tl+tr)/2;
        return merge(get(2*v, tl, tm, l, r), get(2*v+1, tm+1, tr, l, r));
    }
}
*/
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n >> q;
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        ar[a[i]].a = i;
    }
    for(int i = 0; i < n; ++i){
        cin >> b[i];
        ar[b[i]].b = i;
    }
    for(int i = 0; i < n; ++i){
        cin >> c[i];
        ar[c[i]].c = i;
    }
    for(int i = 0; i < n; ++i)
        update(1, 0, n-1, i);

    while(q--){
        int t;
        cin >> t;
        if(t == 1){
            int x;
            cin >> x;
            if(seg[1].v.size() > 0 && *seg[1].v.begin() < getmini(ar[x]))
                cout << "NE\n";
            else
                cout << "DA\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);
                swap(a[p1.a], a[p2.a]);
            }
            if(x == 2){
                swap(p1.b, p2.b);
                swap(b[p1.b], b[p2.b]);
            }
            if(x == 3){
                swap(p1.c, p2.c);
                swap(c[p1.c], c[p2.c]);
            }
            update(1, 0, n-1, p1.a);
            update(1, 0, n-1, p1.b);
            update(1, 0, n-1, p1.c);
            
            update(1, 0, n-1, p2.a);
            update(1, 0, n-1, p2.b);
            update(1, 0, n-1, p2.c);
            
        }
    }
}

Compilation message

tenis.cpp: In function 'node merge(node, node)':
tenis.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(it1 < a.v.size() || it2 < b.v.size()){
           ~~~~^~~~~~~~~~~~
tenis.cpp:36:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(it1 < a.v.size() || it2 < b.v.size()){
                               ~~~~^~~~~~~~~~~~
tenis.cpp:37:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(it1 == a.v.size())
            ~~~~^~~~~~~~~~~~~
tenis.cpp:39:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         else if(it2 == b.v.size())
                 ~~~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12920 KB Output is correct
2 Correct 14 ms 12920 KB Output is correct
3 Correct 14 ms 12920 KB Output is correct
4 Correct 14 ms 12920 KB Output is correct
5 Correct 14 ms 12920 KB Output is correct
6 Correct 15 ms 12920 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12920 KB Output is correct
2 Correct 14 ms 12920 KB Output is correct
3 Correct 14 ms 12920 KB Output is correct
4 Correct 14 ms 12920 KB Output is correct
5 Correct 14 ms 12920 KB Output is correct
6 Correct 15 ms 12920 KB Output is correct
7 Correct 15 ms 12924 KB Output is correct
8 Correct 15 ms 12920 KB Output is correct
9 Correct 20 ms 12928 KB Output is correct
10 Correct 19 ms 12920 KB Output is correct
11 Correct 48 ms 12920 KB Output is correct
12 Correct 15 ms 13048 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12920 KB Output is correct
2 Correct 14 ms 12920 KB Output is correct
3 Correct 14 ms 12920 KB Output is correct
4 Correct 14 ms 12920 KB Output is correct
5 Correct 14 ms 12920 KB Output is correct
6 Correct 15 ms 12920 KB Output is correct
7 Correct 15 ms 12924 KB Output is correct
8 Correct 15 ms 12920 KB Output is correct
9 Correct 20 ms 12928 KB Output is correct
10 Correct 19 ms 12920 KB Output is correct
11 Correct 48 ms 12920 KB Output is correct
12 Correct 15 ms 13048 KB Output is correct
13 Correct 265 ms 16284 KB Output is correct
14 Correct 195 ms 16248 KB Output is correct
15 Correct 159 ms 16248 KB Output is correct
16 Correct 211 ms 16248 KB Output is correct
17 Execution timed out 1061 ms 16256 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 19192 KB Output is correct
2 Correct 224 ms 18908 KB Output is correct
3 Correct 235 ms 19056 KB Output is correct
4 Execution timed out 1074 ms 17852 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12920 KB Output is correct
2 Correct 14 ms 12920 KB Output is correct
3 Correct 14 ms 12920 KB Output is correct
4 Correct 14 ms 12920 KB Output is correct
5 Correct 14 ms 12920 KB Output is correct
6 Correct 15 ms 12920 KB Output is correct
7 Correct 15 ms 12924 KB Output is correct
8 Correct 15 ms 12920 KB Output is correct
9 Correct 20 ms 12928 KB Output is correct
10 Correct 19 ms 12920 KB Output is correct
11 Correct 48 ms 12920 KB Output is correct
12 Correct 15 ms 13048 KB Output is correct
13 Correct 265 ms 16284 KB Output is correct
14 Correct 195 ms 16248 KB Output is correct
15 Correct 159 ms 16248 KB Output is correct
16 Correct 211 ms 16248 KB Output is correct
17 Execution timed out 1061 ms 16256 KB Time limit exceeded
18 Halted 0 ms 0 KB -