oj.uz

Submission #329086

# Submission time Handle Problem Language Result Execution time Memory
329086 2020-11-19T00:48:14 Z Mackerel_Pike Tram (CEOI13_tram) C++14
100 / 100
 57 ms 17132 KB 
#include<bits/stdc++.h>

using namespace std;

#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define PB push_back
#define MP make_pair
#define PH push
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double Lf;
typedef pair<ll, int> pii;

const int maxn = 1.5e5 + 5;
const int maxq = 3e4 + 5;
const int maxl = 15;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, q;
int ans[maxn];

class Data{
public:
	int lid, lmsk, rid, rmsk;
	pii res;
	Data(){}
	Data(int lid_, int lmsk_, int rid_, int rmsk_, pii res_): lid(lid_), lmsk(lmsk_), rid(rid_), rmsk(rmsk_), res(res_){}
};

inline ll dis(int id, int msk, int x, int y){ return 1ll * abs(id - x) * abs(id - x) + (((1 << y) & msk) == 0); }
inline pii &umax(pii &x, const pii &y){ return x = (MP(x.fst, -x.snd) < MP(y.fst, -y.snd) ? y : x); }
inline pii border(int id, int x, int msk){ return MP(1ll * id * id + (msk != 3), x << 1 | (msk == 1)); }

inline pii calc(int lid, int lmsk, int rid, int rmsk){
	pii ret = MP(-INF, -1);
	if(!~lid || !~rid || lid == rid - 1)
		return ret;
	FOR(x, lid + rid >> 1, (lid + rid >> 1) + 2) FOR(y, 0, 2)
		ret = umax(ret, MP(min(dis(lid, lmsk, x, y), dis(rid, rmsk, x, y)), x << 1 | y));
	return ret;
}

inline Data operator + (const Data &a, const Data &b){
	Data c(~a.lid ? a.lid : b.lid, ~a.lid ? a.lmsk : b.lmsk, ~b.rid ? b.rid : a.rid, ~b.rid ? b.rmsk : a.rmsk, MP(-1, -1));
	umax(c.res, a.res);
	umax(c.res, b.res);
	umax(c.res, calc(a.rid, a.rmsk, b.lid, b.lmsk));
	return c;
}

class SegmentTree{
private:
	static const int siz = 262144;
public:
	Data dat[siz << 1];
	inline int size(){ return siz; }
	
	inline void build(){
		FOR(i, siz, siz << 1)
			dat[i] = Data(-1, 0, -1, 0, MP(-1, i - siz));
		for(int i = siz - 1; i; --i)
			dat[i] = dat[i << 1] + dat[i << 1 | 1];
		return;
	}
	inline void update(int y){
		int r = y & 1, c = y >> 1;
		int x = c + siz;
		dat[x].lmsk = dat[x].rmsk = dat[x].lmsk ^ (1 << r);
		dat[x].lid = dat[x].rid = (dat[x].lmsk ? c : -1);
		if(dat[x].lmsk != 3)
			dat[x].res = MP(1, c << 1 | (dat[x].lmsk & 1));
		else
			dat[x].res = MP(-1, -1);
		for(x >>= 1; x; x >>= 1)
			dat[x] = dat[x << 1] + dat[x << 1 | 1];
		return;
	}
} seg;

int main(){
	scanf("%d%d", &n, &q);
	
	seg.build();
	
	FOR(i, 0, q){
		char buf[maxl]; scanf("%s", buf);
		if(buf[0] == 'E'){
			Data x = seg.dat[1];
			if(!~x.lid)
				x.res = MP(INF, 0);
			else{
				if(x.lid)
					umax(x.res, border(x.lid, 0, x.lmsk));
				if(x.rid != n - 1)
					umax(x.res, border(n - x.rid - 1, n - 1, x.rmsk));
			}
			printf("%d %d\n", (x.res.snd >> 1) + 1, (x.res.snd & 1) + 1);
			seg.update(x.res.snd);
			ans[i] = x.res.snd;
		}
		else{
			int x; scanf("%d", &x); --x;
			seg.update(ans[x]);
		}
	}
	return 0;
}

Compilation message

tram.cpp: In function 'pii calc(int, int, int, int)':
tram.cpp:42:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |  FOR(x, lid + rid >> 1, (lid + rid >> 1) + 2) FOR(y, 0, 2)
      |         ~~~~^~~~~
tram.cpp:5:35: note: in definition of macro 'FOR'
    5 | #define FOR(i, x, y) for(int i = (x); i < (y); ++i)
      |                                   ^
tram.cpp:42:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |  FOR(x, lid + rid >> 1, (lid + rid >> 1) + 2) FOR(y, 0, 2)
      |                          ~~~~^~~~~
tram.cpp:5:44: note: in definition of macro 'FOR'
    5 | #define FOR(i, x, y) for(int i = (x); i < (y); ++i)
      |                                            ^
tram.cpp: In function 'int main()':
tram.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
tram.cpp:90:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |   char buf[maxl]; scanf("%s", buf);
      |                   ~~~~~^~~~~~~~~~~
tram.cpp:106:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  106 |    int x; scanf("%d", &x); --x;
      |           ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16748 KB Output is correct
2 Correct 17 ms 16796 KB Output is correct
3 Correct 17 ms 16748 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16748 KB Output is correct
2 Correct 17 ms 16748 KB Output is correct
3 Correct 16 ms 16748 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 16748 KB Output is correct
2 Correct 19 ms 16748 KB Output is correct
3 Correct 17 ms 16748 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16748 KB Output is correct
2 Correct 19 ms 16748 KB Output is correct
3 Correct 21 ms 16748 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 17132 KB Output is correct
2 Correct 49 ms 17004 KB Output is correct
3 Correct 41 ms 17004 KB Output is correct

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 17132 KB Output is correct
2 Correct 44 ms 16876 KB Output is correct
3 Correct 57 ms 17004 KB Output is correct