oj.uz

Submission #113633

# Submission time Handle Problem Language Result Execution time Memory
113633 2019-05-27T08:39:06 Z cki86201 Tram (CEOI13_tram) C++11
100 / 100
 82 ms 6440 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb push_back
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

int A[150050], N, M;

typedef pair<ll, pii> plp;
set <plp> Sx;
set <int> X;

plp get_segment(int l, int r) {
	int m = (l + r) / 2;
	if(l == 0) m = 1;
	else if(r == N+1) m = N;
	vector <pii> v, w;
	for(int dx=-1;dx<=1;dx++) for(int y=1;y<=2;y++) {
		if(l < m+dx && m+dx < r) v.pb(pii(m+dx, y));
	}
	if(l != 0 && (A[l] & 1)) w.pb(pii(l, 1));
	if(l != 0 && (A[l] & 2)) w.pb(pii(l, 2));
	if(r <= N && (A[r] & 1)) w.pb(pii(r, 1));
	if(r <= N && (A[r] & 2)) w.pb(pii(r, 2));
	ll mx = 0;
	pii res = pii(-1, -1);
	for(pii e : v) {
		ll mn = 1e18;
		for(pii f : w) mn = min(mn, (ll)(e.Fi-f.Fi) * (e.Fi-f.Fi) + (ll)(e.Se-f.Se) * (e.Se-f.Se));
		if(mx < mn) mx = mn, res = e;
	}
	return make_pair(-mx, res);
}

void Del(int x) {
	if(A[x] == 0) return;
	X.erase(x);
	auto it = X.lower_bound(x);
	int rx = *it; int lx = *(--it);
	if(A[x] == 1) Sx.erase(plp(-1, pii(x, 2)));
	else if(A[x] == 2) Sx.erase(plp(-1, pii(x, 1)));
	if(lx + 1 < x) Sx.erase(get_segment(lx, x));
	if(x + 1 < rx) Sx.erase(get_segment(x, rx));
	A[x] = 0;
	Sx.insert(get_segment(lx, rx));
}

void Ins(int x, int ax) {
	if(ax == 0) return;
	auto it = X.lower_bound(x);
	int rx = *it; int lx = *(--it);
	Sx.erase(get_segment(lx, rx));
	A[x] = ax;
	if(lx + 1 < x) Sx.insert(get_segment(lx, x));
	if(x + 1 < rx) Sx.insert(get_segment(x, rx));
	if(A[x] == 1) Sx.insert(plp(-1, pii(x, 2)));
	else if(A[x] == 2) Sx.insert(plp(-1, pii(x, 1)));
	X.insert(x);
}

pii save[150050];
int main() {
	scanf("%d%d", &N, &M);
	A[0] = A[N+1] = 3;
	Sx.insert(get_segment(0, N+1));
	X.insert(0); X.insert(N+1);
	for(int i=1;i<=M;i++) {
		char ch[2];
		scanf("%s", ch);
		if(ch[0] == 'E') {
			pii p = Sx.begin()->Se;
			int t = A[p.Fi];
			Del(p.Fi);
			Ins(p.Fi, t ^ p.Se);
			save[i] = p;
			printf("%d %d\n", p.Fi, p.Se);
		}
		else {
			int x; scanf("%d", &x);
			pii p = save[x];
			int t = A[p.Fi];
			Del(p.Fi);
			Ins(p.Fi, t ^ p.Se);
		}
	}
	return 0;
}

Compilation message

tram.cpp: In function 'int main()':
tram.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
tram.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   94 |   scanf("%s", ch);
      |   ~~~~~^~~~~~~~~~
tram.cpp:104:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |    int x; scanf("%d", &x);
      |           ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 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 3 ms 364 KB Output is correct
3 Correct 3 ms 364 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2332 KB Output is correct
2 Correct 43 ms 748 KB Output is correct
3 Correct 57 ms 2028 KB Output is correct

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 6440 KB Output is correct
2 Correct 42 ms 748 KB Output is correct
3 Correct 82 ms 2772 KB Output is correct