Submission #966800

#TimeUsernameProblemLanguageResultExecution timeMemory
966800jcelinTenis (COI19_tenis)C++14
100 / 100
239 ms32852 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> ii; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<ll> vll; typedef vector<pll> vpll; #define PB push_back #define PF push_front #define PPB pop_back #define PPF pop_front #define X first #define Y second #define MP make_pair #define all(x) (x).begin(), (x).end() const int mod = 1e9 + 7; //998244353; const int inf = 1e9 + 7; const ll INF = 1e18 + 7; const int logo = 20; const int MAXN = 1e6 + 7; const int off = 1 << logo; const int trsz = off << 1; const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, -1, 1}; int ps[5][MAXN], n, q; ii merge(ii a, ii b){ if(a.X <= b.X) return a; return b; } struct tournament{ ii seg[trsz]; int p[trsz]; tournament(){ for(int i=off; i<trsz; i++) seg[i].Y = i - off; for(int i=off-1; i>=0; i--) seg[i] = merge(seg[i * 2], seg[i * 2 + 1]); } void prop(int x){ if(p[x] == 0) return; seg[x].X += p[x]; if(x < off) p[x * 2] += p[x], p[x * 2 + 1] += p[x]; p[x] = 0; } void update(int x, int lo, int hi, int a, int b, int vl){ prop(x); if(lo >= b or hi <= a) return; if(lo >= a and hi <= b){ p[x] = vl; prop(x); return; } int mid = (lo + hi) / 2; update(x * 2, lo, mid, a, b, vl); update(x * 2 + 1, mid, hi, a, b, vl); seg[x] = merge(seg[x * 2], seg[x * 2 + 1]); } void upd(int l, int r, int vl){ update(1, 0, off, l, r, vl); } }t; int getv(int x){ int rt = 0; for(int i=1; i<=3; i++) rt = max(rt, ps[i][x]); return rt; } void ad(int x, int vl){ int a = getv(x); t.upd(a, n + 1, vl); } void solve(){ cin >> n >> q; for(int j=1; j<=3; j++){ for(int i=1; i<=n; i++){ int x; cin >> x; ps[j][x] = i; } } t.upd(0, 1, 1); for(int i=1; i<=n; i++) t.upd(i, n + 1, 1); for(int i=1; i<=n; i++) ad(i, -1); while(q--){ int ty, x, y, z; cin >> ty >> x; if(ty == 2){ cin >> y >> z; ad(y, 1); ad(z, 1); swap(ps[x][y], ps[x][z]); ad(y, -1); ad(z, -1); continue; } if(t.seg[1].Y < getv(x)) cout << "NE\n"; else cout << "DA\n"; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int tt = 1; //cin >> tt; while(tt--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...