Submission #626415

#	Time	Username	Problem	Language	Result	Execution time	Memory
626415		TheLostCookie	Catfish Farm (IOI22_fish)	C++17	100 / 100	257 ms	31784 KiB

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) {
	vi inc(M+N,0), dec(M+N,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) {
		int l = lower_bound(all(pts), ii{i,0}) - begin(pts);
		int r = lower_bound(all(pts), ii{i+1,0}) - begin(pts);
		
		vector<vi> colInc(3,vi(r-l,0));
		vi colDec(r-l,0);
		
		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][j-l]=max(colInc[0][j-l],colInc[0][j-1-l]);
			while(p<int(pts.size())&&pts[p].fi==i-2&&pts[p].se<=pts[j].se) {
				colInc[0][j-l]=max(colInc[0][j-l],dec[p]);
				p++;
			}
		}
		FOR(j,l,r) colInc[0][j-l] += 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][0] = max(colInc[1][0],dec[p]+countFish(i-1,0,pts[p].se-1,lPtr[0],rPtr[0])),p++;
		}
		FOR(j,l+1,r) colInc[1][j-l] = max(colInc[1][j-l],colInc[1][j-1-l]);
		
		p = lower_bound(all(pts), ii{i-1,0}) - begin(pts);
		FOR(j,l,r) {
			if(j>l) colInc[2][j-l]=max(colInc[2][j-l],colInc[2][j-1-l]+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][j-l]=max(colInc[2][j-l],inc[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[j-l]=max(colDec[j-l],colDec[j+1-l]+ptw[j].se);
			while(p>=0&&pts[p].fi==i-1&&pts[p].se>=pts[j].se) {
				colDec[j-l]=max(colDec[j-l],dec[p]+countFish(i,pts[j].se,pts[p].se-1,lPtr[0],rPtr[0]));
				p--;
			}
		}
		
		FOR(j,l,r) {
			FOR(k,0,3) {
				inc[j] = max(inc[j],colInc[k][j-l]);
			}
			dec[j] = max(dec[j],colDec[j-l]);
		}
		dec[r-1] = max(inc[r-1],dec[r-1]);
	}

	lli ans = max(*max_element(all(inc)),*max_element(all(dec)));

	return ans;
}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 14 / 14
• Subtask 8: 16 / 16