| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 274849 |
2020-08-19T17:17:13 Z |
arnold518 |
Tram (CEOI13_tram) |
C++14 |
|
136 ms |
9644 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 3e5;
const int MAXM = 3e4;
int N, Q, A[MAXN+10];
pii ans[MAXN+10];
map<int, int> M;
struct Point
{
ll d; int x, y; int l, r;
Point() : d(-1), l(-1), r(-1) {}
Point(ll d, int x, int y, int l, int r) : d(d), x(x), y(y), l(l), r(r) {}
bool operator < (const Point &p) const
{
if(d==p.d)
{
if(x==p.x)
{
return y<p.y;
}
return x<p.x;
}
return d>p.d;
}
};
set<Point> S;
ll dist(ll x1, ll y1, ll x2, ll y2)
{
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
vector<Point> get(int l, int r)
{
vector<Point> V;
{
int x1=l, x2=r;
int y1=M[l], y2=M[r];
int nx, ny;
if(y1==3) y1=1; if(y2==3) y2=1;
nx=(x1+x2)/2, ny=1;
ll now=min(dist(nx, ny, x1, y1), dist(nx, ny, x2, y2));
V.push_back(Point(now, nx, ny, l, r));
nx=(x1+x2)/2+1, ny=1;
now=min(dist(nx, ny, x1, y1), dist(nx, ny, x2, y2));
V.push_back(Point(now, nx, ny, l, r));
}
{
int x1=l, x2=r;
int y1=M[l], y2=M[r];
int nx, ny;
if(y1==3) y1=2; if(y2==3) y2=2;
nx=(x1+x2)/2, ny=2;
ll now=min(dist(nx, ny, x1, y1), dist(nx, ny, x2, y2));
V.push_back(Point(now, nx, ny, l, r));
nx=(x1+x2)/2+1, ny=2;
now=min(dist(nx, ny, x1, y1), dist(nx, ny, x2, y2));
V.push_back(Point(now, nx, ny, l, r));
}
return V;
}
void push(Point p)
{
vector<Point> V;
if(p.l!=-1 && p.r!=-1)
{
V=get(p.l, p.r);
for(auto it : V) S.erase(it);
}
M[p.x]+=p.y;
auto it=M.find(p.x);
if(it!=M.begin())
{
V=get(prev(it)->first, it->first);
for(auto it : V) S.insert(it);
}
if(next(it)!=M.end())
{
V=get(it->first, next(it)->first);
for(auto it : V) S.insert(it);
}
}
void pop(int x, int y)
{
vector<Point> V;
auto it=M.find(x);
if(it!=M.begin())
{
V=get(prev(it)->first, it->first);
for(auto it : V) S.erase(it);
}
if(next(it)!=M.end())
{
V=get(it->first, next(it)->first);
for(auto it : V) S.erase(it);
}
M[x]-=y;
if(M[x]!=0)
{
auto it=M.find(x);
if(it!=M.begin())
{
V=get(prev(it)->first, it->first);
for(auto it : V) S.insert(it);
}
if(next(it)!=M.end())
{
V=get(it->first, next(it)->first);
for(auto it : V) S.insert(it);
}
}
else
{
M.erase(x);
auto it=M.lower_bound(x);
if(it==M.end() || it==M.begin()) return;
V=get(prev(it)->first, it->first);
for(auto it : V) S.insert(it);
}
}
int main()
{
scanf("%d%d", &N, &Q);
for(int i=1; i<=Q; i++)
{
char c;
scanf(" %c", &c);
if(c=='E') A[i]=-1;
else scanf("%d", &A[i]);
}
for(int i=1; i<=Q; i++)
{
if(A[i]==-1)
{
Point p;
if(M.empty())
{
ans[i]={1, 1};
p.x=1; p.y=1;
push(p);
printf("%d %d\n", 1, 1);
continue;
}
if(!S.empty()) p=*S.begin();
{
int x1=M.begin()->first, y1=M.begin()->second;
if(y1==3) y1=1;
int nx=1, ny=1;
ll now=dist(nx, ny, x1, y1);
p=min(p, Point(now, nx, ny, -1, -1));
}
{
int x1=M.begin()->first, y1=M.begin()->second;
if(y1==3) y1=2;
int nx=1, ny=2;
ll now=dist(nx, ny, x1, y1);
p=min(p, Point(now, nx, ny, -1, -1));
}
{
int x1=(--M.end())->first, y1=(--M.end())->second;
if(y1==3) y1=1;
int nx=N, ny=1;
ll now=dist(nx, ny, x1, y1);
p=min(p, Point(now, nx, ny, -1, -1));
}
{
int x1=(--M.end())->first, y1=(--M.end())->second;
if(y1==3) y1=2;
int nx=N, ny=2;
ll now=dist(nx, ny, x1, y1);
p=min(p, Point(now, nx, ny, -1, -1));
}
ans[i]={p.x, p.y};
push(p);
printf("%d %d\n", p.x, p.y);
}
else
{
int x=ans[A[i]].first, y=ans[A[i]].second;
pop(x, y);
}
}
}
Compilation message
tram.cpp: In function 'std::vector<Point> get(int, int)':
tram.cpp:48:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
48 | if(y1==3) y1=1; if(y2==3) y2=1;
| ^~
tram.cpp:48:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
48 | if(y1==3) y1=1; if(y2==3) y2=1;
| ^~
tram.cpp:63:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
63 | if(y1==3) y1=2; if(y2==3) y2=2;
| ^~
tram.cpp:63:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
63 | if(y1==3) y1=2; if(y2==3) y2=2;
| ^~
tram.cpp: In function 'int main()':
tram.cpp:140:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
140 | scanf("%d%d", &N, &Q);
| ~~~~~^~~~~~~~~~~~~~~~
tram.cpp:144:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
144 | scanf(" %c", &c);
| ~~~~~^~~~~~~~~~~
tram.cpp:146:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
146 | else scanf("%d", &A[i]);
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
620 KB |
Output is correct |
| 2 |
Correct |
5 ms |
364 KB |
Output is correct |
| 3 |
Correct |
5 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
620 KB |
Output is correct |
| 2 |
Correct |
5 ms |
364 KB |
Output is correct |
| 3 |
Correct |
6 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
748 KB |
Output is correct |
| 2 |
Correct |
7 ms |
364 KB |
Output is correct |
| 3 |
Correct |
5 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
748 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
96 ms |
3436 KB |
Output is correct |
| 2 |
Correct |
105 ms |
1004 KB |
Output is correct |
| 3 |
Correct |
103 ms |
2924 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
136 ms |
9644 KB |
Output is correct |
| 2 |
Correct |
94 ms |
1004 KB |
Output is correct |
| 3 |
Correct |
101 ms |
3308 KB |
Output is correct |
