| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 62807 |
2018-07-30T06:41:40 Z |
Benq |
Tram (CEOI13_tram) |
C++11 |
|
66 ms |
6124 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 30001;
set<pair<ll,pi>> cans;
set<int> cur;
int n,m;
pi pos[MX];
bool in[150001][2];
void mod(pair<ll,pi> a, int x) {
if (x == 1) cans.insert(a);
else cans.erase(a);
}
void zz(int a, int b, int t, int x ) {
F0R(i,2) {
ll dis0 = (ll)(a-t)*(a-t)+(a!=-MOD&&!in[a][i]);
ll dis1 = (ll)(b-t)*(b-t)+(b!=MOD&&!in[b][i]);
// if (z) cout << "BLAH " << t << " " << a << " " << in[a][0] << " " << in[a][1] << " " << dis0 << " " << dis1 << "\n";
mod({-min(dis0,dis1),{t,i}},x);
}
}
void tri(int a, int b, int x, int z = 0) { // [a,b)
int t = (a+b)/2;
t = max(t,1); t = min(t,n);
// cout << "ZZ " << a << " " << b << " " << x << "\n";
zz(a,b,t,x);
if (t-1 >= a) zz(a,b,t,x);
}
void ad(int ind) {
//cout << "HI\n";
pos[ind] = cans.begin()->s;
/*if (pos[ind] == mp(4,0)) {
cout << "AH " << in[3][1] << "\n";
tri(3,4,1,1);
for (auto a: cur) cout << "AA " << a << "\n";
for (auto a: cans) cout << "OH " << a.f << " " << a.s.f << " " << a.s.s << "\n";
}*/
auto it = cur.lb(pos[ind].f);
if (*it == pos[ind].f) {
tri(*prev(it),*it,-1), tri(*it,*next(it),-1);
} else {
tri(*prev(it),*it,-1);
}
in[pos[ind].f][pos[ind].s] = 1;
cur.insert(pos[ind].f);
it = cur.find(pos[ind].f);
tri(*prev(it),*it,1), tri(*it,*next(it),1);
// for (auto a: cans) cout << "AH " << a.f << " " << a.s.f << " " << a.s.s << "\n";
}
void del(int ind) {
auto it = cur.find(pos[ind].f);
tri(*prev(it),*it,-1);
tri(*it,*next(it),-1);
in[pos[ind].f][pos[ind].s] = 0;
if (in[pos[ind].f][0] || in[pos[ind].f][1]) {
tri(*prev(it),*it,1);
tri(*it,*next(it),1);
} else {
tri(*prev(it),*next(it),1);
cur.erase(it);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
cur.insert(-MOD), cur.insert(MOD);
tri(-MOD,MOD,1);
// for (auto a: cans) cout << a.f << " " << a.s.f << " " << a.s.s << "\n";
FOR(i,1,m+1) {
char c; cin >> c;
if (c == 'E') {
ad(i);
cout << pos[i].f << " " << pos[i].s+1 << "\n";
} else {
int p; cin >> p;
del(p);
}
// cout << in[3][1] << "\n";
}
}
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/
| # |
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 |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
876 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
876 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 |
52 ms |
3436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
6124 KB |
Output is correct |
| 2 |
Incorrect |
46 ms |
876 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
