| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 264497 |
2020-08-14T07:15:31 Z |
문홍윤(#5092) |
Tram (CEOI13_tram) |
C++17 |
|
52 ms |
4332 KB |
#include <bits/stdc++.h>
#define F first
#define S second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
const LL INF=8e18;
int n, q, re, llin[150010], rlin[150010], rv[150010];
bool ch[150010][3];
pii ans[150010];
pair<LL, pii> get_max(int s, int e){
pair<LL, pii> ret=mp(-INF, mp(-1, -1));
int x[4]={s, (s+e)/2, (s+e)/2+1, e};
for(int i=0; i<4; i++){
if(x[i]>e)continue;
for(int j=0; j<2; j++){
LL d=INF;
for(int i2=0; i2<4; i2+=3){
for(int j2=0; j2<2; j2++){
if(!ch[x[i2]][j2])continue;
d=min(d, (LL)(x[i]-x[i2])*(x[i]-x[i2])+(LL)(j-j2)*(j-j2));
}
}
ret=max(ret, mp(d, mp(-x[i], -j)));
}
}
if(ret.F==-1)return mp(INF, mp(-s, 0));
return ret;
}
set<pair<pair<LL, pii>, pii> > s;
int main(){
scanf("%d %d", &n, &q);
pair<pair<LL, pii>, pii> non;
non.S.F=1, non.S.S=n;
rlin[1]=n;
llin[n]=1;
non.F=get_max(1, n);
s.insert(non);
for(int i=1; i<=q; i++){
char c;
scanf(" %c", &c);
if(c=='E'){
pair<pair<LL, pii>, pii> nw=*s.rbegin();
s.erase(nw);
ans[++re]=mp(-nw.F.S.F, -nw.F.S.S);
rv[i]=re;
rlin[nw.S.F]=ans[re].F;
llin[nw.S.S]=ans[re].F;
llin[ans[re].F]=nw.S.F;
rlin[ans[re].F]=nw.S.S;
pair<pair<LL, pii>, pii> l, r;
l.S.F=nw.S.F, l.S.S=ans[re].F;
r.S.F=ans[re].F, r.S.S=nw.S.S;
ch[ans[re].F][ans[re].S]=true;
l.F=get_max(l.S.F, l.S.S);
r.F=get_max(r.S.F, r.S.S);
s.insert(l);
s.insert(r);
}
else{
int num;
scanf("%d", &num);
num=rv[num];
pair<pair<LL, pii>, pii> l, r;
l.S.F=llin[ans[num].F], l.S.S=ans[num].F;
r.S.F=ans[num].F, r.S.S=rlin[ans[num].F];
l.F=get_max(l.S.F, l.S.S);
r.F=get_max(r.S.F, r.S.S);
s.erase(l);
s.erase(r);
llin[ans[num].F]=0;
rlin[ans[num].F]=0;
rlin[l.S.F]=r.S.S;
llin[r.S.S]=l.S.F;
ch[ans[num].F][ans[num].S]=false;
pair<pair<LL, pii>, pii> nw;
nw.S.F=l.S.F, nw.S.S=r.S.S;
nw.F=get_max(nw.S.F, nw.S.S);
s.insert(nw);
}
}
for(int i=1; i<=re; i++)printf("%d %d\n", ans[i].F, ans[i].S+1);
}
/*
10 9
E
E
E
E
L 3
E
E
L 6
E
*/
Compilation message
tram.cpp: In function 'int main()':
tram.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
38 | scanf("%d %d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~
tram.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
47 | scanf(" %c", &c);
| ~~~~~^~~~~~~~~~~
tram.cpp:68:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
68 | scanf("%d", &num);
| ~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2028 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2028 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
51 ms |
2412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
4332 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
828 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
