Submission #626335

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
626335	2022-08-11T11:49:27 Z	TheLostCookie	Catfish Farm (IOI22_fish)	C++17	75 / 100	1000 ms	64440 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
    	//uses two pointers for const op
    	function<lli(lli,lli,lli,int&,int&)> countFish = [&] (lli x, lli y1, lli y2, int &l, int &r) {
    		if(x<0||x>=N||y1>y2) return 0LL;
    		else {
			while(l<int(pts.size())&&pts[l] < ii{x,y1}) l++;
    			while(l>0 && pts[l-1] >= ii{x,y1}) l--;
    			while(r<int(pts.size())&&pts[r] <= ii{x,y2}) r++;
    			while(r>0 && pts[r-1] > ii{x,y2}) r--;
    			return wts[r]-wts[l];
    		}
    	};
    	
    	int lPtr[2], rPtr[2];
    	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);
    		lPtr[0] = rPtr[0] = lPtr[1] = rPtr[1] = lower_bound(all(pts), ii{i-1,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,lPtr[0],rPtr[0]);
    		
    		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,lPtr[0],rPtr[0])),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,lPtr[0],rPtr[0]));
    			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,lPtr[1],rPtr[1]));
    				p++;
    			}
    		}
    		
    		p = lower_bound(all(pts), ii{i-1,INF}) - begin(pts);
    		lPtr[0] = rPtr[0] = lower_bound(all(pts), ii{i+1,0}) - begin(pts);
    		ROF(j,l,r) {
    			if(i>0&&j<r-1) colDec[pts[j]]=max(colDec[pts[j]],colDec[pts[j+1]]+ptw[j].se);
    			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,lPtr[0],rPtr[0]));
    				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()); 
    	}
    	
    	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	415 ms	38476 KB	Output is correct
2	Correct	519 ms	47028 KB	Output is correct
3	Correct	78 ms	4804 KB	Output is correct
4	Correct	79 ms	4804 KB	Output is correct
5	Execution timed out	1088 ms	53732 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	847 ms	52728 KB	Output is correct
3	Execution timed out	1042 ms	64440 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	93 ms	4804 KB	Output is correct
2	Correct	75 ms	4756 KB	Output is correct
3	Correct	137 ms	8248 KB	Output is correct
4	Correct	121 ms	7748 KB	Output is correct
5	Correct	190 ms	10664 KB	Output is correct
6	Correct	182 ms	10664 KB	Output is correct
7	Correct	180 ms	10780 KB	Output is correct
8	Correct	182 ms	10668 KB	Output is correct

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	1 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	3 ms	468 KB	Output is correct
11	Correct	2 ms	340 KB	Output is correct
12	Correct	2 ms	340 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	1 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	1 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	3 ms	468 KB	Output is correct
11	Correct	2 ms	340 KB	Output is correct
12	Correct	2 ms	340 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	4 ms	468 KB	Output is correct
17	Correct	92 ms	3292 KB	Output is correct
18	Correct	88 ms	3220 KB	Output is correct
19	Correct	83 ms	3228 KB	Output is correct
20	Correct	92 ms	3260 KB	Output is correct
21	Correct	80 ms	3248 KB	Output is correct
22	Correct	171 ms	6588 KB	Output is correct
23	Correct	17 ms	852 KB	Output is correct
24	Correct	55 ms	2292 KB	Output is correct
25	Correct	2 ms	312 KB	Output is correct
26	Correct	15 ms	852 KB	Output is correct

Subtask #6
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	1 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	3 ms	468 KB	Output is correct
11	Correct	2 ms	340 KB	Output is correct
12	Correct	2 ms	340 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	4 ms	468 KB	Output is correct
17	Correct	92 ms	3292 KB	Output is correct
18	Correct	88 ms	3220 KB	Output is correct
19	Correct	83 ms	3228 KB	Output is correct
20	Correct	92 ms	3260 KB	Output is correct
21	Correct	80 ms	3248 KB	Output is correct
22	Correct	171 ms	6588 KB	Output is correct
23	Correct	17 ms	852 KB	Output is correct
24	Correct	55 ms	2292 KB	Output is correct
25	Correct	2 ms	312 KB	Output is correct
26	Correct	15 ms	852 KB	Output is correct
27	Correct	6 ms	596 KB	Output is correct
28	Correct	472 ms	13848 KB	Output is correct
29	Correct	803 ms	22220 KB	Output is correct
30	Correct	573 ms	22212 KB	Output is correct
31	Correct	560 ms	22364 KB	Output is correct
32	Correct	627 ms	22240 KB	Output is correct
33	Correct	575 ms	22440 KB	Output is correct
34	Correct	559 ms	22316 KB	Output is correct
35	Correct	201 ms	8136 KB	Output is correct
36	Correct	607 ms	22200 KB	Output is correct

Subtask #7
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	93 ms	4804 KB	Output is correct
2	Correct	75 ms	4756 KB	Output is correct
3	Correct	137 ms	8248 KB	Output is correct
4	Correct	121 ms	7748 KB	Output is correct
5	Correct	190 ms	10664 KB	Output is correct
6	Correct	182 ms	10664 KB	Output is correct
7	Correct	180 ms	10780 KB	Output is correct
8	Correct	182 ms	10668 KB	Output is correct
9	Correct	185 ms	10680 KB	Output is correct
10	Correct	153 ms	9480 KB	Output is correct
11	Correct	317 ms	19896 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 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	1 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	78 ms	4808 KB	Output is correct
19	Correct	76 ms	4820 KB	Output is correct
20	Correct	77 ms	4808 KB	Output is correct
21	Correct	78 ms	4804 KB	Output is correct
22	Correct	231 ms	10676 KB	Output is correct
23	Correct	334 ms	19884 KB	Output is correct
24	Correct	310 ms	19896 KB	Output is correct

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	415 ms	38476 KB	Output is correct
2	Correct	519 ms	47028 KB	Output is correct
3	Correct	78 ms	4804 KB	Output is correct
4	Correct	79 ms	4804 KB	Output is correct
5	Execution timed out	1088 ms	53732 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Submission #626335

Compilation message