oj.uz

Submission #264566

# Submission time Handle Problem Language Result Execution time Memory
264566 2020-08-14T07:42:20 Z Namnamseo Tram (CEOI13_tram) C++17
100 / 100
 89 ms 7952 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rrep(i, n) for(int i=1; i<=(n); ++i)

int n, m;
pp history[30001];
char chk[150010][2];

typedef pair<ll,pp> candtype;
auto cmp = [](const candtype& a, const candtype& b){
	return make_tuple(-a.x, a.y) < make_tuple(-b.x, b.y);
};
set<candtype,decltype(cmp)> cand(cmp);

multiset<int> row;

const ll inf = 1ll<<60;

ll dist(ll a, ll b){ return a*a + b*b; }

void get_cand(int l, int r, vector<candtype>& v){
	v.clear();

	if(l+1 == r) return;
	int lb, rb;
	if(l == 0){
		if(r == n+1){
			v.eb(0, pp{1, 0});
			return;
		} else lb = rb = 1;
	} else if(r == n+1) lb = rb = n;
	else lb = (l+r)/2, rb = (l+r+1)/2;

	for(int ri=lb; ri<=rb; ++ri) for(int ci=0; ci<2; ++ci){
		ll md = inf;
		for(int br=l; br<=r; br+=(r-l)) for(int bc=0; bc<2; ++bc){
			if(chk[br][bc]) md = min(md, dist(br-ri, bc-ci));
		}
		if(v.size()){
			ll cv = v.back().first;
			if(cv > md) continue;
			else if(cv < md) v.clear();
		}
		if(v.empty() || v.back().first == md){
			v.eb(md, pp{ri, ci});
		}
	}
}

int get_bef(int r){ return *--row.lower_bound(r); }
int get_nxt(int r){ return *row.upper_bound(r); }

vector<candtype> v;
void Add(int l, int r){ get_cand(l, r, v); for(auto& c:v) cand.insert(c); }
void Del(int l, int r){ get_cand(l, r, v); for(auto& c:v) cand.erase(c); }

int main(){
	read(n, m);
	row.insert(0); row.insert(n+1);
	Add(0, n+1);
	rrep(qi, m){
		static char cmdbuf[5];
		scanf("%s", cmdbuf);
		if(cmdbuf[0] == 'E'){
			auto itm = *cand.begin();
			int cr, cc;
			tie(cr, cc) = history[qi] = cand.begin() -> second;
			printf("%d %d\n", cr, cc+1);
			int bef = get_bef(cr), nxt = get_nxt(cr);
			Del(bef, nxt);
			row.insert(cr); chk[cr][cc]=1;
			Add(bef, cr); Add(cr, nxt);

			if(!chk[cr][cc^1]){
				cand.emplace(1, pp{cr, cc^1});
			}
			cand.erase(itm);
		} else {
			int bq; read(bq);
			int r, c; tie(r, c) = history[bq];
			int bef = get_bef(r), nxt = get_nxt(r);
			Del(bef, r); Del(r, nxt);
			chk[r][c] = 0; row.erase(row.find(r));
			if(chk[r][c^1]){
				Add(bef, r); Add(r, nxt);
				cand.emplace(1, pp{r, c});
			} else {
				cand.erase(candtype(1, pp{r, c^1}));
				Add(bef, nxt);
			}
		}
	}
	return 0;
}

Compilation message

tram.cpp: In function 'void read(int&)':
tram.cpp:6:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    6 | void read(int& x){ scanf("%d",&x); }
      |                    ~~~~~^~~~~~~~~
tram.cpp: In function 'void read(ll&)':
tram.cpp:7:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    7 | void read(ll& x){ scanf("%lld",&x); }
      |                   ~~~~~^~~~~~~~~~~
tram.cpp: In function 'int main()':
tram.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |   scanf("%s", cmdbuf);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 492 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 3 ms 492 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 492 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 5 ms 492 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1004 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 4 ms 748 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1004 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 3 ms 748 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 2516 KB Output is correct
2 Correct 35 ms 832 KB Output is correct
3 Correct 59 ms 2284 KB Output is correct

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 7952 KB Output is correct
2 Correct 32 ms 876 KB Output is correct
3 Correct 55 ms 2924 KB Output is correct