oj.uz

Submission #626305

# Submission time Handle Problem Language Result Execution time Memory
626305 2022-08-11T11:19:20 Z TheLostCookie Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 75796 KB 
#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);
	}
	
	//(not effective) 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;
	//const op
	int fishCount, fishIndex0, fishIndex;
	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++;
			}
		}
		
		fishCount = 0, fishIndex = lower_bound(all(pts), ii{i-1,0}) - begin(pts);
		FOR(j,l,r) {
			while(fishIndex < int(pts.size()) && pts[fishIndex].fi == i-1 && pts[fishIndex].se <= pts[j].se-1) fishCount += ptw[fishIndex++].se;
			colInc[0][pts[j]] += fishCount;
		}
		p = lower_bound(all(pts), ii{i-2,0}) - begin(pts);
		fishCount = 0, fishIndex = lower_bound(all(pts), ii{i-1,0}) - begin(pts);
		while(p<int(pts.size())&&pts[p].fi==i-2) {
			while(fishIndex < int(pts.size()) && pts[fishIndex].fi == i-1 && pts[fishIndex].se <= pts[p].se-1) fishCount += ptw[fishIndex++].se;
			colInc[1][pts[l]] = max(colInc[1][pts[l]],dec[pts[p]]+fishCount);
			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]]+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));
				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;
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:56:17: warning: unused variable 'fishIndex0' [-Wunused-variable]
   56 |  int fishCount, fishIndex0, fishIndex;
      |                 ^~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 47620 KB Output is correct
2 Correct 547 ms 57164 KB Output is correct
3 Correct 95 ms 13608 KB Output is correct
4 Correct 88 ms 13540 KB Output is correct
5 Execution timed out 1091 ms 65648 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 869 ms 62740 KB Output is correct
3 Execution timed out 1077 ms 75796 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 13512 KB Output is correct
2 Correct 97 ms 13512 KB Output is correct
3 Correct 145 ms 15652 KB Output is correct
4 Correct 151 ms 15820 KB Output is correct
5 Correct 201 ms 19772 KB Output is correct
6 Correct 206 ms 19880 KB Output is correct
7 Correct 207 ms 19880 KB Output is correct
8 Correct 206 ms 19880 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 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '199038527173'
10 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 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '199038527173'
10 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 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '199038527173'
10 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 13512 KB Output is correct
2 Correct 97 ms 13512 KB Output is correct
3 Correct 145 ms 15652 KB Output is correct
4 Correct 151 ms 15820 KB Output is correct
5 Correct 201 ms 19772 KB Output is correct
6 Correct 206 ms 19880 KB Output is correct
7 Correct 207 ms 19880 KB Output is correct
8 Correct 206 ms 19880 KB Output is correct
9 Correct 203 ms 19880 KB Output is correct
10 Correct 167 ms 12356 KB Output is correct
11 Correct 329 ms 24528 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 272 KB Output is correct
14 Correct 0 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 89 ms 13604 KB Output is correct
19 Correct 106 ms 13512 KB Output is correct
20 Correct 91 ms 13512 KB Output is correct
21 Correct 92 ms 13544 KB Output is correct
22 Correct 253 ms 19256 KB Output is correct
23 Correct 332 ms 24656 KB Output is correct
24 Correct 335 ms 24608 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 47620 KB Output is correct
2 Correct 547 ms 57164 KB Output is correct
3 Correct 95 ms 13608 KB Output is correct
4 Correct 88 ms 13540 KB Output is correct
5 Execution timed out 1091 ms 65648 KB Time limit exceeded
6 Halted 0 ms 0 KB -