Submission #626325

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
626325	2022-08-11T11:43:07 Z	TheLostCookie	Catfish Farm (IOI22_fish)	C++17	75 / 100	1000 ms	64468 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, rPtr;
    	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 = rPtr = 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,rPtr);
    		
    		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,rPtr)),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,rPtr));
    			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,rPtr));
    				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]]+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,rPtr));
    				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	412 ms	38476 KB	Output is correct
2	Correct	507 ms	46952 KB	Output is correct
3	Correct	71 ms	4804 KB	Output is correct
4	Correct	90 ms	4804 KB	Output is correct
5	Execution timed out	1102 ms	53708 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	860 ms	52744 KB	Output is correct
3	Execution timed out	1016 ms	64468 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	74 ms	4828 KB	Output is correct
2	Correct	71 ms	4804 KB	Output is correct
3	Correct	126 ms	8328 KB	Output is correct
4	Correct	119 ms	7804 KB	Output is correct
5	Correct	180 ms	10780 KB	Output is correct
6	Correct	180 ms	10652 KB	Output is correct
7	Correct	180 ms	10676 KB	Output is correct
8	Correct	203 ms	10776 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	0 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	1 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	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	1 ms	340 KB	Output is correct
10	Correct	4 ms	468 KB	Output is correct
11	Correct	1 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	484 KB	Output is correct
17	Correct	90 ms	3268 KB	Output is correct
18	Correct	85 ms	3272 KB	Output is correct
19	Correct	77 ms	3216 KB	Output is correct
20	Correct	78 ms	3224 KB	Output is correct
21	Correct	80 ms	3272 KB	Output is correct
22	Correct	178 ms	6588 KB	Output is correct
23	Correct	15 ms	852 KB	Output is correct
24	Correct	57 ms	2252 KB	Output is correct
25	Correct	3 ms	340 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	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	1 ms	340 KB	Output is correct
10	Correct	4 ms	468 KB	Output is correct
11	Correct	1 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	484 KB	Output is correct
17	Correct	90 ms	3268 KB	Output is correct
18	Correct	85 ms	3272 KB	Output is correct
19	Correct	77 ms	3216 KB	Output is correct
20	Correct	78 ms	3224 KB	Output is correct
21	Correct	80 ms	3272 KB	Output is correct
22	Correct	178 ms	6588 KB	Output is correct
23	Correct	15 ms	852 KB	Output is correct
24	Correct	57 ms	2252 KB	Output is correct
25	Correct	3 ms	340 KB	Output is correct
26	Correct	15 ms	852 KB	Output is correct
27	Correct	6 ms	596 KB	Output is correct
28	Correct	514 ms	13812 KB	Output is correct
29	Correct	813 ms	22328 KB	Output is correct
30	Correct	553 ms	22320 KB	Output is correct
31	Correct	581 ms	22208 KB	Output is correct
32	Correct	641 ms	22348 KB	Output is correct
33	Correct	601 ms	22320 KB	Output is correct
34	Correct	592 ms	22204 KB	Output is correct
35	Correct	234 ms	8256 KB	Output is correct
36	Correct	610 ms	22196 KB	Output is correct

Subtask #7
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	74 ms	4828 KB	Output is correct
2	Correct	71 ms	4804 KB	Output is correct
3	Correct	126 ms	8328 KB	Output is correct
4	Correct	119 ms	7804 KB	Output is correct
5	Correct	180 ms	10780 KB	Output is correct
6	Correct	180 ms	10652 KB	Output is correct
7	Correct	180 ms	10676 KB	Output is correct
8	Correct	203 ms	10776 KB	Output is correct
9	Correct	185 ms	10808 KB	Output is correct
10	Correct	151 ms	9528 KB	Output is correct
11	Correct	309 ms	19896 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	1 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	78 ms	4804 KB	Output is correct
19	Correct	73 ms	4804 KB	Output is correct
20	Correct	71 ms	4804 KB	Output is correct
21	Correct	72 ms	4804 KB	Output is correct
22	Correct	228 ms	10752 KB	Output is correct
23	Correct	327 ms	19944 KB	Output is correct
24	Correct	350 ms	19896 KB	Output is correct

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	412 ms	38476 KB	Output is correct
2	Correct	507 ms	46952 KB	Output is correct
3	Correct	71 ms	4804 KB	Output is correct
4	Correct	90 ms	4804 KB	Output is correct
5	Execution timed out	1102 ms	53708 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Submission #626325

Compilation message