Submission #71524

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
71524	2018-08-25T03:53:12 Z	zigui(#2223)	Logistical Metropolis (KRIII5_LM)	C++11	0 / 7	4 ms	868 KB

LM

#include<assert.h>
#include<tuple>
#include<set>
#include<queue>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;

typedef pair<int,int> pii;

const int MX = 1<<10;
int N, K, ans = 0;
pii D[MX*2];

struct Tree{
	int t[MX*2];
	void update(int x, int v){
		x += MX; t[x] = v;
		while(x > 1){
			x /= 2;
			t[x] = max(t[x*2], t[x*2+1]);
		}
	}
	int read(int s, int e){
		s += MX, e += MX;
		int mx = -1e9;
		while(s <= e){
			if(s&1) mx = max(mx, t[s++]);
			if(~e&1) mx = max(mx, t[e--]);
			s /= 2, e /= 2;
		}
		return mx;
	}
} A;

int deb = 1;
void solve()
{
	vector<int> C[MX];
	int U[MX] = {}, tmp[MX] = {};

	for(int i = 1; i <= K; i++) C[D[i].first].push_back(D[i].second);
	for(int i = 1; i <= N; i++) sort(C[i].begin(), C[i].end());
	for(int i = N; i >= 1; i--){	
		for(int j = 1; j <= N; j++) tmp[j] = 0;
		for(int c : C[i]) tmp[c] = 1;
		int cur = 0;
		for(int j = 1; j <= N; j++){
			if(tmp[j]) cur = 0;
			else cur += 1;
			
			if(cur == 0) U[j] = -1e9;
			else if(cur == 1) U[j] = U[j];
			else U[j] = max(U[j], cur);
		}
		for(int j = 1; j <= N; j++) U[j]++;
		for(int j = 1; j <= N; j++) A.update(j, U[j] + j); // to N

		set<int> B;
		for(int j = 1; j <= N; j++) B.insert(j);
		for(int j = i-1; j >= 1; j--){
			for(int c : C[j]){
				B.erase(c);
				A.update(c, -1e9);
			}
			vector<pii> interval;
			int st = 1;
			for(int c : C[j]){
				if(st != c) interval.emplace_back(st, c-1);
				st = c+1;
			}
			if(st != N+1) interval.emplace_back(st, N);
			
			if(j == i-1) continue; // at least one move required
			for(pii c : interval){
				int s, e; tie(s, e) = c;
				auto it = B.lower_bound(s);
				if(it == B.end() || *it >= e) continue;
				int v = A.read(*it+1, e) - *it + (i-j)*2 - 2;
				ans = max(ans, v);
			}
		}
	}
}

void rot90(){ for(int i = 1; i <= K; i++) D[i] = pii(D[i].second, N+1-D[i].first); }
void flip(){ for(int i = 1; i <= K; i++) D[i].second = N+1 - D[i].second; }

int main()
{
	scanf("%d%d", &N, &K);
	for(int i = 1; i <= K; i++){
		scanf("%d%d", &D[i].first, &D[i].second);
	}
	for(int i = 1; i <= 8; i++){
		solve();
		if(i%4) rot90();
		else flip();
	}
	printf("%d\n", ans);
}

Compilation message

LM.cpp: In function 'int main()':
LM.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~
LM.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &D[i].first, &D[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	4 ms	632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 72.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	4 ms	868 KB	Time limit exceeded (wall clock)
2	Halted	0 ms	0 KB	-