Submission #586858

#	Time	Username	Problem	Language	Result	Execution time	Memory
586858		JovanB	Tenis (COI19_tenis)	C++17	100 / 100	157 ms	8028 KiB

tenis

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 100000;

struct Segment{
    ll sum, mn, pos;
} seg[4*N+5];

int n;

void mrg(int node){
    seg[node].sum = seg[node*2].sum + seg[node*2+1].sum;
    seg[node].mn = min(seg[node*2].mn, seg[node*2].sum + seg[node*2+1].mn);
    if(seg[node*2].sum + seg[node*2+1].mn == seg[node].mn) seg[node].pos = seg[node*2+1].pos;
    else seg[node].pos = seg[node*2].pos;
}

void init(int node, int l, int r){
    if(l == r){
        seg[node].mn = -2*l;
        seg[node].pos = l;
        seg[node].sum = -2*l;
        if(l == n) seg[node].mn = 0;
        return;
    }
    int mid = (l+r)/2;
    init(node*2, l, mid);
    init(node*2+1, mid+1, r);
    mrg(node);
}

void upd(int node, int l, int r, int x, int v){
    if(l == r){
        seg[node].mn += v;
        seg[node].sum += v;
        return;
    }
    int mid = (l+r)/2;
    if(x <= mid) upd(node*2, l, mid, x, v);
    else upd(node*2+1, mid+1, r, x, v);
    mrg(node);
}

int a[N+5], b[N+5], c[N+5];
int pa[N+5], pb[N+5], pc[N+5];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int qrs;
    cin >> n >> qrs;
    for(int i=1; i<=n; i++){
        int x;
        cin >> x;
        pa[x] = n - i + 1;
    }
    init(1, 1, n);
    for(int i=1; i<=n; i++){
        int x;
        cin >> x;
        pb[x] = n - i + 1;
        upd(1, 1, n, pa[x], pb[x]);
    }
    for(int i=1; i<=n; i++){
        int x;
        cin >> x;
        pc[x] = n - i + 1;
        upd(1, 1, n, pa[x], pc[x]);
    }
    while(qrs--){
        int typ;
        cin >> typ;
        if(typ == 1){
            int x;
            cin >> x;
            if(seg[1].mn > 0 || pa[x] > seg[1].pos) cout << "DA\n";
            else cout << "NE\n";
        }
        else{
            int p, a, b;
            cin >> p >> a >> b;
            if(p == 1){
                upd(1, 1, n, pa[a], -pb[a]);
                upd(1, 1, n, pa[a], -pc[a]);
                upd(1, 1, n, pa[b], -pb[b]);
                upd(1, 1, n, pa[b], -pc[b]);
                swap(pa[a], pa[b]);
                upd(1, 1, n, pa[a], pb[a]);
                upd(1, 1, n, pa[a], pc[a]);
                upd(1, 1, n, pa[b], pb[b]);
                upd(1, 1, n, pa[b], pc[b]);
            }
            else if(p == 2){
                upd(1, 1, n, pa[a], -pb[a]);
                upd(1, 1, n, pa[b], -pb[b]);
                swap(pb[a], pb[b]);
                upd(1, 1, n, pa[a], pb[a]);
                upd(1, 1, n, pa[b], pb[b]);
            }
            else{
                upd(1, 1, n, pa[a], -pc[a]);
                upd(1, 1, n, pa[b], -pc[b]);
                swap(pc[a], pc[b]);
                upd(1, 1, n, pa[a], pc[a]);
                upd(1, 1, n, pa[b], pc[b]);
            }
        }
    }
    return 0;
}

/*
4 1
1 2 3 4
2 1 3 4
2 1 3 4
1 4
*/

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