Submission #626214

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
626214	2022-08-11T09:56:34 Z	TheLostCookie	Catfish Farm (IOI22_fish)	C++17	9 / 100	1000 ms	71560 KB

fish

#include <bits/stdc++.h>
#include "fish.h"
using namespace std;

typedef long long int lli;
typedef vector<lli> vi;
typedef pair<int,int> ii;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ROF(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define pb push_back
#define fi first
#define se second
#define all(v) begin(v),end(v)

const int INF = 2e9;

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
	map<ii,lli> inc, dec;
	inc[{-1,-INF}] = inc[{-1,INF}] = 0;
	
	vector<pair<ii,lli>> ptw;
	FOR(i,0,M) ptw.pb({{X[i],Y[i]},W[i]});
	FOR(i,0,N) ptw.pb({{i,INF},0});
	sort(all(ptw));
	
	vector<ii> pts;
	vector<lli> wts{0};
	FOR(i,0,M+N) {
		pts.pb(ptw[i].fi);
		wts.pb(wts.back()+ptw[i].se);
	}
	
	//counts fish in [{x,y1},{x,y2}], inclusive of endpoints
	function<lli(lli,lli,lli)> countFish = [&] (lli x, lli y1, lli y2) {
		if(y1 > y2) return 0LL;
		else {
			int l = lower_bound(all(pts),ii{x,y1}) - begin(pts);
			int r = upper_bound(all(pts),ii{x,y2}) - begin(pts);
			return wts[r]-wts[l];
		}
	};
	
	FOR(i,0,N) {
		map<ii,lli> colInc[3];
		map<ii,lli> colDec;
	
		int l = lower_bound(all(pts), ii{i,0}) - begin(pts);
		int r = lower_bound(all(pts), ii{i+1,0}) - begin(pts);
		
		int p = lower_bound(all(pts), ii{i-2,0}) - begin(pts);
		FOR(j,l,r) {
			if(j>l) colInc[0][pts[j]]=max(colInc[0][pts[j]],colInc[0][pts[j-1]]);
			while(p<int(pts.size())&&pts[p].fi==i-2&&pts[p].se<=pts[j].se) {
				colInc[0][pts[j]]=max(colInc[0][pts[j]],dec[pts[p]]);
				p++;
			}
		}
		FOR(j,l,r) colInc[0][pts[j]] += countFish(i-1,0,pts[j].se-1);
		p = lower_bound(all(pts), ii{i-2,0}) - begin(pts);
		while(p<int(pts.size())&&pts[p].fi==i-2) colInc[1][pts[l]] = max(colInc[1][pts[l]],dec[pts[p]]+countFish(i-1,0,pts[p].se-1)),p++;
		FOR(j,l+1,r) colInc[1][pts[j]] = max(colInc[1][pts[j]],colInc[1][pts[j-1]]);
		
		p = lower_bound(all(pts), ii{i-1,0}) - begin(pts);
		FOR(j,l,r) {
			if(j>l) colInc[2][pts[j]]=max(colInc[2][pts[j]],colInc[2][pts[j-1]]+countFish(i-1,pts[j-1].se,pts[j].se-1));
			while(p<int(pts.size())&&pts[p].fi==i-1&&pts[p].se<=pts[j].se) {
				colInc[0][pts[j]]=max(colInc[0][pts[j]],inc[pts[p]]+countFish(i-1,pts[p].se,pts[j].se-1));
				p++;
			}
		}
		
		p = lower_bound(all(pts), ii{i-1,INF}) - begin(pts);
		ROF(j,l,r) {
			if(i>0&&j<r-1) colDec[pts[j]]=max(colDec[pts[j]],colDec[pts[j+1]]+countFish(i,pts[j].se,pts[j+1].se-1));
			while(p>=0&&pts[p].fi==i-1&&pts[p].se>=pts[j].se) {
				colDec[pts[j]]=max(colDec[pts[j]],dec[pts[p]]+countFish(i,pts[j].se,pts[p].se-1));
				p--;
			}
		}
		
		FOR(j,l,r) {
			FOR(k,0,3) {
				inc[pts[j]] = max(inc[pts[j]],colInc[k][pts[j]]);
			}
			dec[pts[j]] = max(dec[pts[j]],colDec[pts[j]]);
		}
		dec[ii{i,INF}] = max(inc[ii{i,INF}],dec[ii{i,INF}]);
	}
	
	lli ans = max(inc[{N-1,INF}],dec.lower_bound({N-1,0})->second);
	
	return ans;
}

Subtask #1
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	592 ms	38520 KB	Output is correct
2	Correct	725 ms	46896 KB	Output is correct
3	Correct	249 ms	15984 KB	Output is correct
4	Correct	248 ms	15976 KB	Output is correct
5	Execution timed out	1083 ms	71560 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Execution timed out	1089 ms	52600 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	257 ms	15904 KB	Output is correct
2	Correct	252 ms	15840 KB	Output is correct
3	Correct	360 ms	24884 KB	Output is correct
4	Correct	332 ms	23340 KB	Output is correct
5	Correct	531 ms	34440 KB	Output is correct
6	Correct	576 ms	34368 KB	Output is correct
7	Correct	529 ms	34344 KB	Output is correct
8	Correct	547 ms	34420 KB	Output is correct

Subtask #4
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	2 ms	340 KB	Output is correct
10	Correct	7 ms	724 KB	Output is correct
11	Incorrect	2 ms	468 KB	1st lines differ - on the 1st token, expected: '278622587073', found: '277471986209'
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	2 ms	340 KB	Output is correct
10	Correct	7 ms	724 KB	Output is correct
11	Incorrect	2 ms	468 KB	1st lines differ - on the 1st token, expected: '278622587073', found: '277471986209'
12	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	2 ms	340 KB	Output is correct
10	Correct	7 ms	724 KB	Output is correct
11	Incorrect	2 ms	468 KB	1st lines differ - on the 1st token, expected: '278622587073', found: '277471986209'
12	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	257 ms	15904 KB	Output is correct
2	Correct	252 ms	15840 KB	Output is correct
3	Correct	360 ms	24884 KB	Output is correct
4	Correct	332 ms	23340 KB	Output is correct
5	Correct	531 ms	34440 KB	Output is correct
6	Correct	576 ms	34368 KB	Output is correct
7	Correct	529 ms	34344 KB	Output is correct
8	Correct	547 ms	34420 KB	Output is correct
9	Correct	564 ms	34352 KB	Output is correct
10	Incorrect	413 ms	26988 KB	1st lines differ - on the 1st token, expected: '36454348383152', found: '36359530063629'
11	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	592 ms	38520 KB	Output is correct
2	Correct	725 ms	46896 KB	Output is correct
3	Correct	249 ms	15984 KB	Output is correct
4	Correct	248 ms	15976 KB	Output is correct
5	Execution timed out	1083 ms	71560 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Submission #626214

Compilation message