Submission #492974

#	Time	Username	Problem	Language	Result	Execution time	Memory
492974		Habitus	Tenis (COI19_tenis)	C++14	100 / 100	126 ms	6596 KiB

tenis

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define dec(x, y) fixed << setprecision((y)) << (x)
#define xx first
#define yy second
#define srt(v) sort((v).begin(), (v).end())
#define srtr(v) sort((v).rbegin(), (v).rend())
#define pb push_back
#define popb pop_back
#define sz(a) (int)(a).size()
#define len(a) (int)(a).length()
#define mp make_pair
#define endl "\n"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int n, q, gde[100002][3];
struct ralf {
    int vr, lazy;
} st[400002];
void prop(int node, int tl, int tr) {
    st[node].vr+=st[node].lazy;
    if(tl!=tr) {
        st[2*node].lazy+=st[node].lazy;
        st[2*node+1].lazy+=st[node].lazy;
    }
    st[node].lazy=0;
}
void build(int node, int tl, int tr) {
    if(tl==tr) {
        st[node].vr=tl;
        return;
    }
    int mid=(tl+tr)/2;
    build(2*node, tl, mid);
    build(2*node+1, mid+1, tr);
    st[node].vr=min(st[2*node].vr, st[2*node+1].vr);
}
void upd(int node, int tl, int tr, int gl, int gr, int val) {
    prop(node, tl, tr);
    if(tl>=gl && tr<=gr) {
        st[node].lazy+=val;
        return;
    }
    int mid=(tl+tr)/2;
    if(mid>=gl) upd(2*node, tl, mid, gl, gr, val);
    if(mid+1<=gr) upd(2*node+1, mid+1, tr, gl, gr, val);
    prop(2*node, tl, mid);
    prop(2*node+1, mid+1, tr);
    st[node].vr=min(st[2*node].vr, st[2*node+1].vr);
}
int query(int node, int tl, int tr) {
    prop(node, tl, tr);
    if(tl==tr) return tl;
    int mid=(tl+tr)/2;
    prop(2*node, tl, mid);
    if(st[2*node].vr==0) return query(2*node, tl, mid);
    return query(2*node+1, mid+1, tr);
}
int main() {
    ios;
    cin >> n >> q;
    for(int i=0; i<3; i++) {
        for(int j=1; j<=n; j++) {
            int x; cin >> x;
            gde[x][i]=j;
        }
    }
    build(1, 1, n);
    for(int i=1; i<=n; i++) {
        int d=max(max(gde[i][0], gde[i][1]), gde[i][2]);
        upd(1, 1, n, d, n, -1);
    }
    while(q--) {
        int t, x;
        cin >> t >> x;
        if(t==1) {
            int uzmi=query(1, 1, n);
            if(max(max(gde[x][0], gde[x][1]), gde[x][2])<=uzmi) cout << "DA" << endl;
            else cout << "NE" << endl;
        }
        else {
            int y, z; cin >> y >> z;
            x--;
            int stari1=max(max(gde[y][0], gde[y][1]), gde[y][2]), stari2=max(max(gde[z][0], gde[z][1]), gde[z][2]);
            int novi1=gde[z][x], novi2=gde[y][x];
            gde[y][x]=novi1, gde[z][x]=novi2;
            novi1=max(max(gde[y][0], gde[y][1]), gde[y][2]), novi2=max(max(gde[z][0], gde[z][1]), gde[z][2]);
            if(novi1>stari1) {
                upd(1, 1, n, stari1, novi1-1, 1);
            }
            else if(novi1<stari1) {
                upd(1, 1, n, novi1, stari1-1, -1);
            }
            if(novi2>stari2) {
                upd(1, 1, n, stari2, novi2-1, 1);
            }
            else if(novi2<stari2) {
                upd(1, 1, n, novi2, stari2-1, -1);
            }
        }
    }
    return 0;
}

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