| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 53251 |
2018-06-29T05:45:14 Z |
윤교준(#1402) |
Tram (CEOI13_tram) |
C++11 |
|
62 ms |
4588 KB |
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
//#define rf(x) (x)=0;while(*p<48)im=*p=='-';while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);if(im)(x)=-(x);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define cb(x) (x)=(!(x))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define INFST (0x7f7f7f7f)
#define INFLLST (0x7f7f7f7f7f7f7f7fll)
using namespace std;
typedef long long ll;
typedef __int128_t lll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ld, ld> pdd;
typedef complex<ld> base;
const ld EPS = (ld)1e-7;
const ld PI = acos(0) * 2;
bool isZero(const ld& x) { return abs(x) <= EPS; }
int sign(const ld& x) { return isZero(x) ? 0 : (0 < x ? 1 : -1); }
ll gcd(ll a, ll b) { for(;b;a%=b,swap(a,b)){} return abs(a); }
pll operator + (const pll& a, const pll& b) { return pll(a.first+b.first, a.second+b.second); }
pll operator - (const pll& a, const pll& b) { return pll(a.first-b.first, a.second-b.second); }
pll operator * (const pll& a, const ll& b) { return pll(a.first*b, a.second*b); }
ll operator * (const pll& a, const pll& b) { return a.first*b.second - b.first*a.second; }
ll ccw(const pll& a, const pll& b, const pll& c) { return a*b + b*c + c*a; }
int rd(int s, int e) { return rand()%(e-s+1) + s; }
void fg(vector<int> G[], int a, int b) { G[a].pb(b); G[b].pb(a); }
void fg(vector<pii> G[], int a, int b, int c) { G[a].pb({b, c}); G[b].pb({a, c}); }
ll pw(ll n) { return n*n; }
ll dst(ll y0, ll x0, ll y1, ll x1) { return pw(y1-y0) + pw(x1-x0); }
const int MAXN = 150005;
const int MAXQ = 30005;
struct NOD {
NOD(int s, int e, ll c, int y, int x)
: s(s), e(e), c(c), y(y), x(x) {}
int s, e;
ll c;
int y, x;
bool operator < (const NOD &t) const {
if(c != t.c) return c > t.c;
if(y != t.y) return y < t.y;
if(x != t.x) return x < t.x;
if(s != t.s) return s < t.s;
return e < t.e;
}
void f(int &_s, int &_e, int &_y, int &_x) const {
_s = s; _e = e; _y = y; _x = x;
}
void print() {
printf("%d %d :: %lld : %d %d\n", s, e, c, y, x);
}
};
set<NOD> TQ;
set<int> TC;
bool B[MAXN][3];
int A[MAXQ];
int AnsY[MAXQ], AnsX[MAXQ];
int N, Q;
NOD f(int _s, int _e) {
int s = max(1, _s), e = min(N, _e);
int hy = -1, hx = -1; ll hl = -INFLL;
vector<pii> HV;
{
int m = (s+e)/2;
HV.eb(s, 1); HV.eb(s, 2);
HV.eb(e, 1); HV.eb(e, 2);
HV.eb(m, 1); HV.eb(m, 2);
HV.eb(m+1, 1); HV.eb(m+1, 2);
}
vector<pii> TV;
{
if(B[s][1]) TV.eb(s, 1);
if(B[s][2]) TV.eb(s, 2);
if(B[e][1]) TV.eb(e, 1);
if(B[e][2]) TV.eb(e, 2);
}
for(auto &hyx : HV) {
int y, x; tie(y, x) = hyx;
if(y < s || e < y || B[y][x]) continue;
ll ret = INFLL;
for(auto &tyx : TV) {
ll t = dst(tyx.first, tyx.second, y, x);
if(t < ret) ret = t;
}
if(hl < ret) {
hl = ret;
hy = y; hx = x;
} else if(hl == ret && pii(y, x) < pii(hy, hx)) {
hy = y; hx = x;
}
}
return NOD(_s, _e, hl, hy, hx);
}
int main() {
scanf("%d%d", &N, &Q);
for(int i = 1; i <= Q; i++) {
char c; scanf(" %c", &c);
if('E' == c) {
A[i] = -1;
continue;
}
scanf("%d", &A[i]);
}
TC.insert(-INF); TC.insert(INF);
TQ.insert(f(-INF, INF));
for(int qi = 1; qi <= Q; qi++) {
//printf("QUERY %d\n", qi);
if(A[qi] < 0) {
int s, e, y, x;
TQ.begin() -> f(s, e, y, x);
for(; !TQ.empty();) {
auto it = TQ.begin();
if(it -> y == y && it -> x == x) TQ.erase(it);
else break;
}
AnsY[qi] = y; AnsX[qi] = x;
//printf("GET ANS %d : %d %d\n", qi, y, x);
if(B[y][1] || B[y][2]) {
{
NOD ret = f(s, y);
auto it = TQ.find(ret);
if(TQ.end() != it) TQ.erase(it);
}
{
NOD ret = f(y, e);
auto it = TQ.find(ret);
if(TQ.end() != it) TQ.erase(it);
}
}
B[y][x] = true;
if(s != y) {
TQ.insert(f(s, y));
}
if(e != y) {
TQ.insert(f(y, e));
}
TC.insert(y);
} else {
int y = AnsY[A[qi]], x = AnsX[A[qi]];
int s = -1, e = -1;
auto tcit = TC.find(y);
{
auto utcit = tcit; utcit--;
s = *utcit;
NOD ret = f(s, y);
auto it = TQ.find(ret);
if(TQ.end() != it) TQ.erase(it);
}
{
auto dtcit = tcit; dtcit++;
e = *dtcit;
NOD ret = f(y, e);
auto it = TQ.find(ret);
if(TQ.end() != it) TQ.erase(it);
}
B[y][x] = false;
if(!B[y][1] && !B[y][2]) {
TC.erase(y);
TQ.insert(f(s, e));
} else {
TQ.insert(f(s, y));
TQ.insert(f(y, e));
}
}
}
for(int i = 1; i <= Q; i++)
if(A[i] < 0)
printf("%d %d\n", AnsY[i], AnsX[i]);
return 0;
}
Compilation message
tram.cpp: In function 'int main()':
tram.cpp:128:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
128 | scanf("%d%d", &N, &Q);
| ~~~~~^~~~~~~~~~~~~~~~
tram.cpp:130:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
130 | char c; scanf(" %c", &c);
| ~~~~~^~~~~~~~~~~
tram.cpp:135:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
135 | scanf("%d", &A[i]);
| ~~~~~^~~~~~~~~~~~~
| # |
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 |
4 ms |
492 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 |
Correct |
5 ms |
1004 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1004 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
2156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
4588 KB |
Output is correct |
| 2 |
Runtime error |
8 ms |
876 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
