Submission #626296

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
626296	2022-08-11T11:06:07 Z	TheLostCookie	Catfish Farm (IOI22_fish)	C++17	75 / 100	1000 ms	75760 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;
	ptw.reserve(M+N);
	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;
	FOR(i,0,M+N) {
		pts.pb(ptw[i].fi);
	}
	
	//const op
	vector<vector<int>> cols(N);
	vector<vi> wts(N);
	FOR(i,0,M+N) {
		int c = ptw[i].fi.fi,r=ptw[i].fi.se;
		cols[c].pb(r);
		if(wts[c].empty()) wts[c].pb(0);
		wts[c].pb(wts[c].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(x < 0 || x >= N || y1 > y2) return 0LL;
		else {
			int l = lower_bound(all(cols[x]),y1) - begin(cols[x]);
			int r = upper_bound(all(cols[x]),y2) - begin(cols[x]);
			return wts[x][r]-wts[x][l];
		}
	};
	
	map<ii,lli> colInc[3];
	map<ii,lli> colDec;
	FOR(i,0,N) {	
		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[2][pts[j]]=max(colInc[2][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}]);
		
		while(!inc.empty() && inc.begin()->fi.fi < i-1) inc.erase(inc.begin());
		while(!dec.empty() && dec.begin()->fi.fi < i-1) dec.erase(dec.begin());
		FOR(j,0,3) colInc[j].clear();
		colDec.clear();
	}
	
	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	416 ms	47656 KB	Output is correct
2	Correct	527 ms	57308 KB	Output is correct
3	Correct	86 ms	13604 KB	Output is correct
4	Correct	83 ms	13500 KB	Output is correct
5	Execution timed out	1087 ms	65496 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	Correct	882 ms	62792 KB	Output is correct
3	Execution timed out	1095 ms	75760 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	91 ms	13604 KB	Output is correct
2	Correct	115 ms	13600 KB	Output is correct
3	Correct	138 ms	15644 KB	Output is correct
4	Correct	134 ms	16012 KB	Output is correct
5	Correct	201 ms	20028 KB	Output is correct
6	Correct	192 ms	20240 KB	Output is correct
7	Correct	218 ms	20264 KB	Output is correct
8	Correct	203 ms	20224 KB	Output is correct

Subtask #4
14.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	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	4 ms	468 KB	Output is correct
11	Correct	2 ms	340 KB	Output is correct
12	Correct	3 ms	488 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	2 ms	340 KB	Output is correct

Subtask #5
21.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	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	4 ms	468 KB	Output is correct
11	Correct	2 ms	340 KB	Output is correct
12	Correct	3 ms	488 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	2 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	5 ms	468 KB	Output is correct
17	Correct	121 ms	3292 KB	Output is correct
18	Correct	98 ms	4260 KB	Output is correct
19	Correct	89 ms	4136 KB	Output is correct
20	Correct	90 ms	4140 KB	Output is correct
21	Correct	96 ms	4088 KB	Output is correct
22	Correct	196 ms	7360 KB	Output is correct
23	Correct	18 ms	1100 KB	Output is correct
24	Correct	65 ms	2764 KB	Output is correct
25	Correct	3 ms	324 KB	Output is correct
26	Correct	17 ms	1016 KB	Output is correct

Subtask #6
17.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	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	4 ms	468 KB	Output is correct
11	Correct	2 ms	340 KB	Output is correct
12	Correct	3 ms	488 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	2 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	5 ms	468 KB	Output is correct
17	Correct	121 ms	3292 KB	Output is correct
18	Correct	98 ms	4260 KB	Output is correct
19	Correct	89 ms	4136 KB	Output is correct
20	Correct	90 ms	4140 KB	Output is correct
21	Correct	96 ms	4088 KB	Output is correct
22	Correct	196 ms	7360 KB	Output is correct
23	Correct	18 ms	1100 KB	Output is correct
24	Correct	65 ms	2764 KB	Output is correct
25	Correct	3 ms	324 KB	Output is correct
26	Correct	17 ms	1016 KB	Output is correct
27	Correct	6 ms	820 KB	Output is correct
28	Correct	556 ms	15632 KB	Output is correct
29	Correct	889 ms	21560 KB	Output is correct
30	Correct	672 ms	19672 KB	Output is correct
31	Correct	686 ms	19616 KB	Output is correct
32	Correct	731 ms	21780 KB	Output is correct
33	Correct	717 ms	19768 KB	Output is correct
34	Correct	689 ms	19672 KB	Output is correct
35	Correct	232 ms	8464 KB	Output is correct
36	Correct	737 ms	21040 KB	Output is correct

Subtask #7
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	91 ms	13604 KB	Output is correct
2	Correct	115 ms	13600 KB	Output is correct
3	Correct	138 ms	15644 KB	Output is correct
4	Correct	134 ms	16012 KB	Output is correct
5	Correct	201 ms	20028 KB	Output is correct
6	Correct	192 ms	20240 KB	Output is correct
7	Correct	218 ms	20264 KB	Output is correct
8	Correct	203 ms	20224 KB	Output is correct
9	Correct	220 ms	19996 KB	Output is correct
10	Correct	177 ms	12588 KB	Output is correct
11	Correct	329 ms	24920 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	84 ms	13608 KB	Output is correct
19	Correct	85 ms	13604 KB	Output is correct
20	Correct	88 ms	13564 KB	Output is correct
21	Correct	85 ms	13608 KB	Output is correct
22	Correct	238 ms	19560 KB	Output is correct
23	Correct	369 ms	24940 KB	Output is correct
24	Correct	364 ms	25388 KB	Output is correct

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	416 ms	47656 KB	Output is correct
2	Correct	527 ms	57308 KB	Output is correct
3	Correct	86 ms	13604 KB	Output is correct
4	Correct	83 ms	13500 KB	Output is correct
5	Execution timed out	1087 ms	65496 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Submission #626296

Compilation message