| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 160631 |
2019-10-29T02:13:33 Z |
lyc |
Tram (CEOI13_tram) |
C++14 |
|
1000 ms |
5868 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)
const int MX_M = 30005;
int N, M;
map<int, int> tram;
set<pair<ll,ii> > cp;
ii rec[MX_M];
bool opp(int c, ii p) {
return (p.sc & (1<<c)) == 0;
}
ll f(int r, int c, ii p) {
//cout << "f " << r << " " << c << " from " << p.fi << " " << p.sc << " opp " << opp(c,p) << endl;
return (ll) (p.fi - r) * (p.fi - r) + opp(c, p);
}
ll eval(int r, int c) {
ll res;
if (tram.empty()) res = 0;
else if (tram.count(r) && (tram[r] & (1<<c))) res = -1;
else {
auto j = tram.lower_bound(r);
if (j == tram.begin()) res = f(r,c,*j);
else {
auto i = prev(j);
res = min(f(r,c,*i), f(r,c,*j));
}
}
//cout << "EVAL " << r << " " << c << " :: " << res << endl;
return res;
//return min(f(r,c,*i), f(r,c,*j));
}
void addLoc(ii p) {
if ((tram[p.fi] ^ (1<<p.sc)) == 0) cp.insert(iii(1,ii(p.fi,!p.sc)));
else {
auto it = cp.find(iii(1,p));
if (it != cp.end()) cp.erase(it);
}
tram[p.fi] |= (1<<p.sc);
}
void delLoc(ii p) {
if ((tram[p.fi] ^ (1<<p.sc)) != 0) cp.insert(iii(1,p));
else {
auto it = cp.find(iii(1,ii(p.fi,!p.sc)));
if (it != cp.end()) cp.erase(it);
}
tram[p.fi] |= (1<<p.sc);
tram[p.fi] &= ~(1<<p.sc);
if (tram[p.fi] == 0) tram.erase(p.fi);
}
ld intersect(int c, ii p, ii q) {
return ((ld) q.fi * q.fi + opp(c, q) - (ld) p.fi * p.fi - opp(c,p)) / (2.0 * (q.fi - p.fi));
}
pair<ll,ii> getCP(int c, ii p, ii q) {
ld x = intersect(c,p,q);
int a = (int)round(floor(x)), b = (int)round(ceil(x));
ll av = min(f(a,c,p),f(a,c,q)), bv = min(f(b,c,p),f(b,c,q));
//cout << x << endl;
//cout << "candidates " << a << "," << av << " and " << b << "," << bv << endl;
if (av >= bv) return mp(-av,ii(a,c));
else return mp(-bv,ii(b,c));
}
void addCP(int c, ii p, ii q) {
if (p.fi+1 == q.fi) return;
auto pqCP = getCP(c,p,q);
cp.insert(pqCP);
//cout << "add " << pqCP.fi << " " << pqCP.sc.fi << " " << pqCP.sc.sc << endl;
}
void delCP(int c, ii p, ii q) {
if (p.fi+1 == q.fi) return;
auto pqCP = getCP(c,p,q);
//cout << "del " << pqCP.fi << " " << pqCP.sc.fi << " " << pqCP.sc.sc << endl;
auto it = cp.find(pqCP);
if (it != cp.end()) cp.erase(it);
}
void dbg() {
cout << "==========================================" << endl;
cout << "TRAM: ";
for (auto x : tram) cout << "(" << x.fi << "," << x.sc << ") ";
cout << endl;
cout << "CP: ";
for (auto x : cp) cout << "(" << x.fi << "," << x.sc.fi << "," << x.sc.sc << ") ";
cout << endl;
cout << "==========================================" << endl;
cout << endl;
}
int main() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
FOR(Mi,1,M){
char T; cin >> T;
if (T == 'E') {
// get the maximum of points and extrema as loc
pair<ll,ii> best = mp(-2,ii(-1,-1));
ll tmp;
if ((tmp = eval(N,1)) >= best.fi) best = mp(tmp,ii(N,1));
if ((tmp = eval(N,0)) >= best.fi) best = mp(tmp,ii(N,0));
if ((tmp = eval(1,1)) >= best.fi) best = mp(tmp,ii(1,1));
if ((tmp = eval(1,0)) >= best.fi) best = mp(tmp,ii(1,0));
if (!cp.empty() && (-cp.begin()->fi > best.fi || (-cp.begin()->fi == best.fi && (cp.begin()->sc.fi < best.sc.fi || (cp.begin()->sc.fi == best.sc.fi && cp.begin()->sc.sc < best.sc.sc)))))
best = *cp.begin(), cp.erase(cp.begin());
// record loc;
rec[Mi] = best.sc;
// add loc to tram
addLoc(rec[Mi]);
map<int,int>::iterator it = tram.lower_bound(best.sc.fi), jt;
// remove old point btw prev and next
if (it != tram.begin() && next(it) != tram.end()) {
delCP(0,*prev(it),*next(it));
delCP(1,*prev(it),*next(it));
}
// add new point with prev, if any
if (it != tram.begin()) {
addCP(0,*prev(it),*it);
addCP(1,*prev(it),*it);
}
// add new point with next
if (next(it) != tram.end()) {
addCP(0,*it,*next(it));
addCP(1,*it,*next(it));
}
// print ans
cout << rec[Mi].fi << " " << rec[Mi].sc+1 << endl;
} else {
int P; cin >> P;
// retrieve loc
ii loc = rec[P];
map<int,int>::iterator it = tram.lower_bound(loc.fi), jt;
// remove old point with prev
if (it != tram.begin()) {
delCP(0,*prev(it),*it);
delCP(1,*prev(it),*it);
}
// remove old point with next
if (next(it) != tram.end()) {
delCP(0,*it,*next(it));
delCP(1,*it,*next(it));
}
// add new point btw prev and next
if (it != tram.begin() && next(it) != tram.end()) {
addCP(0,*prev(it),*next(it));
addCP(1,*prev(it),*next(it));
}
// remove loc from tram
delLoc(loc);
}
//dbg();
}
}
| # |
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 |
7 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
620 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 |
9 ms |
620 KB |
Output is correct |
| 2 |
Execution timed out |
1073 ms |
364 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
112 ms |
1912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
5868 KB |
Output is correct |
| 2 |
Execution timed out |
1081 ms |
620 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
