| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 144197 |
2019-08-16T09:54:44 Z |
Abelyan |
Tenis (COI19_tenis) |
C++17 |
|
500 ms |
17044 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa
const int N=1e5+10;
const ll MOD2=998244353;
const ll MOD=1e9+7;
void yes(){
cout<<"DA"<<endl;
}
void no(){
cout<<"NE"<<endl;
}
/*
struct node{
set<int> s[3],tarb[3][3];
int qan;
node(){qan=0;}
};
set<int>::iterator it;
node sg[4*N];
void ad(int v,int tl,int tr,int ind,int ham,int val){
sg[v].s[ham].insert(val);
FOR(i,3){
if (ham==i)continue;
it=sg[v].tarb[i][ham].find(val);
if (it==sg[v].tarb[i][ham].end()){
sg[v].tarb[ham][i].insert(val);
sg[v].qan++;
}
else{
sg[v].tarb[i][ham].erase(it);
sg[v].qan--;
}
}
if (tl==tr)return;
int tm=(tl+tr)/2;
if (ind<=tm)ad(v+v,tl,tm,ind,ham,val);
else ad(v+v+1,tm+1,tr,ind,ham,val);
}
void rem(int v,int tl,int tr,int ind,int ham,int val){
sg[v].s[ham].erase(val);
FOR(i,3){
if (ham==i)continue;
it=sg[v].tarb[ham][i].find(val);
if (it!=sg[v].tarb[ham][i].end()){
sg[v].tarb[ham][i].erase(it);
sg[v].qan--;
}
else{
sg[v].tarb[i][ham].insert(val);
sg[v].qan++;
}
}
if (tl==tr)return;
int tm=(tl+tr)/2;
if (ind<=tm)rem(v+v,tl,tm,ind,ham,val);
else rem(v+v+1,tm+1,tr,ind,ham,val);
}
int n,q;
int query(int v,int tl,int tr){
if (sg[v].qan==0 && tr!=n-1) return tr-tl+1;
if (tl==tr)return -1;
int tm=(tl+tr)/2;
int ans=query(v+v,tl,tm);
if (query(v+v,tl,tm)==tm-tl+1){
return tm-tl+1+query(v+v+1,tm+1,tr);
}
return ans;
}
*/
int a[3][N],ind[3][N];
int n,q,qan;
set<int> s[3],tarb[3][3];
set<int>::iterator it;
void ins(int ham,int val){
s[ham].insert(val);
FOR(i,3){
if (ham==i)continue;
it=tarb[i][ham].find(val);
if (it==tarb[i][ham].end()){
tarb[ham][i].insert(val);
qan++;
}
else{
tarb[i][ham].erase(it);
qan--;
}
}
}
int get(){
int pat=-1;
qan=0;
FOR(i,n-1){
//cout<<a[0][i]<<" "<<a[1][i]<<" "<<a[2][i]<<endl;
ins(0,a[0][i]);
ins(1,a[1][i]);
ins(2,a[2][i]);
//cout<<qan<<" ";
if (!qan)pat=i;
}
//cout<<endl;
FOR(i,3){
s[i].clear();
FOR(j,3){
tarb[i][j].clear();
}
}
return pat;
}
int main(){
fastio;
srng;
cin>>n>>q;
FOR(i,3)
FORD(j,n){
cin>>a[i][j];
//ad(1,0,n-1,j,i,a[i][j]);
ind[i][a[i][j]]=j;
}
int pat=get();
cout<<pat<<endl;
FOR(i,q){
int tp;
cin>>tp;
if (tp==1){
int x;
cin>>x;
//cout<<query(1,0,n-1)<<endl;
if (ind[0][x]<=pat)no();
else yes();
}
else{
int tp,v,u;
cin>>tp>>v>>u;
tp--;
/*
int indv=ind[tp][v];
int indu=ind[tp][u];
rem(1,0,n-1,indv,tp,v);
ad(1,0,n-1,indv,tp,u);
rem(1,0,n-1,indu,tp,u);
ad(1,0,n-1,indu,tp,v);
*/
swap(ind[tp][v],ind[tp][u]);
a[tp][ind[tp][v]]=v;
a[tp][ind[tp][u]]=u;
pat=get();
//cout<<pat<<endl;
}
}
return 0;
}
/*
7 2 8
C 1
C 2
C 3
C 4
C 5
C 6
O 7
O 7
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
664 ms |
17044 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
