Submission #328926

#	Time	Username	Problem	Language	Result	Execution time	Memory
328926		Mackerel_Pike	Tram (CEOI13_tram)	C++14	100 / 100	72 ms	17132 KiB

tram

#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 bool comp(const pii &a, const pii &b){ return MP(a.fst, MP(-a.snd % n, -a.snd / n)) < MP(b.fst, MP(-b.snd % n, -b.snd / n)); }

inline pii max(const pii &a, const pii &b){ return comp(a, b) ? b : a; }

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 calc(int lid, int lmsk, int rid, int rmsk){
	pii ret = MP(-INF, -1);
	if(!~lid || !~rid || lid == rid - 1)
		return ret;
	int x = (lid + rid) >> 1, y = 0;
	FOR(i, 0, 2) FOR(j, 0, 2){
		pii cur = MP(min(dis(lid, lmsk, x + i, y + j), dis(rid, rmsk, x + i, y + j)), (y + j) * n + (x + i));
		ret = max(ret, cur);
	}
	return ret;
}

inline Data operator + (const Data &a, const Data &b){
	Data c;
	c.lid = (!~a.lid ? b.lid : a.lid), c.lmsk = (!~a.lid ? b.lmsk : a.lmsk);
	c.rid = (!~b.rid ? a.rid : b.rid); c.rmsk = (!~b.rid ? a.rmsk : b.rmsk);
	c.res = max(a.res, b.res);
	c.res = max(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(int x, int l, int r){
		if(l == r){
			dat[x] = Data(-1, 0, -1, 0, MP(-INF, l));
			return;
		}
		int md = l + r >> 1;
		build(x << 1, l, md);
		build(x << 1 | 1, md + 1, r);
		dat[x] = dat[x << 1] + dat[x << 1 | 1];
		return;
	}
	inline void update(int x, int l, int r, int y){
		if(l == r){
			int row = y / n;
			dat[x].lmsk ^= (1 << row);
			dat[x].rmsk ^= (1 << row);
			dat[x].lid = dat[x].rid = (dat[x].lmsk ? l : -1);
			if(dat[x].lmsk != 3){
				dat[x].res = MP(1, ((dat[x].lmsk & 1) ? 1 : 0) * n + l);
			}
			else
				dat[x].res = MP(-INF, -1);
			return;
		}
		int md = l + r >> 1;
		int column = y % n;
		if(column <= md)
			update(x << 1, l, md, y);
		else
			update(x<< 1 | 1, md + 1, r, y);
		dat[x] = dat[x << 1] + dat[x << 1 | 1];
		return;
	}
} seg;

int main(){
	
	scanf("%d%d", &n, &q);
	
	seg.build(1, 0, seg.size() - 1);
	
	FOR(i, 0, q){
		char buf[maxl]; scanf("%s", buf);
		if(buf[0] == 'E'){
			Data fuck = seg.dat[1];
			pii vl, vr;
			if(!~fuck.lid && !~fuck.rid)
				fuck.res = MP(INF, 0);
			else{
				if(fuck.lid){
					int &lid = fuck.lid, &lmsk = fuck.lmsk;
					if(fuck.lmsk != 3)
						vl = MP(1ll * lid * lid + 1, ((lmsk & 1) ? 1 : 0) * n + 0);
					else
						vl = MP(1ll * lid * lid, 0);
					fuck.res = max(fuck.res, vl);
				}
				if(fuck.rid != n - 1){
					int &rid = fuck.rid, &rmsk = fuck.rmsk;
					if(fuck.rmsk != 3)
						vr = MP(1ll * (n - rid - 1) * (n - rid - 1) + 1, ((rmsk & 1) ? 1 : 0) * n + n - 1);
					else
						vr = MP(1ll * (n - rid - 1) * (n - rid - 1), n - 1);
					fuck.res = max(fuck.res, vr);
				}
			}
			printf("%d %d\n", fuck.res.snd % n + 1, fuck.res.snd / n + 1);
			seg.update(1, 0, seg.size() - 1, fuck.res.snd);
			ans[i] = fuck.res.snd;
		}
		else{
			int x; scanf("%d", &x); --x;
			seg.update(1, 0, seg.size() - 1, ans[x]);
		}
	}
	return 0;
}

Compilation message (stderr)

tram.cpp: In member function 'void SegmentTree::build(int, int, int)':
tram.cpp:75:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |   int md = l + r >> 1;
      |            ~~^~~
tram.cpp: In member function 'void SegmentTree::update(int, int, int, int)':
tram.cpp:94:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |   int md = l + r >> 1;
      |            ~~^~~
tram.cpp: In function 'int main()':
tram.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
tram.cpp:112:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  112 |   char buf[maxl]; scanf("%s", buf);
      |                   ~~~~~^~~~~~~~~~~
tram.cpp:141:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  141 |    int x; scanf("%d", &x); --x;
      |           ~~~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 15 / 15
• Subtask 8: 20 / 20