제출 #692952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
692952		Pyqe	메기 농장 (IOI22_fish)	C++17	100 / 100	715 ms	43956 KiB

fish

#include <bits/stdc++.h>
#include "fish.h"

using namespace std;

#define mp make_pair
#define fr first
#define sc second

const long long inf=1e18;
long long mxa[100069][2];
vector<pair<long long,long long>> vl[100069];

struct segtree
{
	long long l,r,mx;
	segtree *p[2];
	
	void bd(long long lh,long long rh)
	{
		l=lh;
		r=rh;
		mx=-inf;
		if(l<r)
		{
			long long ii,md=(l+r)/2;
			
			for(ii=0;ii<2;ii++)
			{
				p[ii]=new segtree;
				p[ii]->bd(!ii?l:md+1,!ii?md:r);
			}
		}
	}
	void ud(long long x,long long w)
	{
		if(l>x||r<x);
		else if(l>=x&&r<=x)
		{
			mx=max(mx,w);
		}
		else
		{
			long long ii;
			
			for(ii=0;ii<2;ii++)
			{
				p[ii]->ud(x,w);
			}
			mx=max(p[0]->mx,p[1]->mx);
		}
	}
	long long qr(long long lh,long long rh)
	{
		if(l>rh||r<lh)
		{
			return -inf;
		}
		else if(l>=lh&&r<=rh)
		{
			return mx;
		}
		else
		{
			return max(p[0]->qr(lh,rh),p[1]->qr(lh,rh));
		}
	}
}
sg[2];

long long max_weights(int n,int m,vector<int> xa,vector<int> ya,vector<int> wg)
{
	long long i,j,ii,x,y,w,l,l2,sz,z=-inf;
	
	for(i=1;i<=m;i++)
	{
		x=xa[i-1]+1;
		y=ya[i-1]+1;
		w=wg[i-1];
		vl[x].push_back({y,w});
	}
	for(ii=0;ii<2;ii++)
	{
		sg[ii].bd(1,n);
	}
	for(i=1;i<=n;i++)
	{
		sort(vl[i].begin(),vl[i].end());
		l=mxa[i-1][1];
		l2=-inf;
		if(i-2>=0)
		{
			l2=max(mxa[i-2][0],mxa[i-2][1]);
		}
		sz=vl[i].size();
		for(j=0;j<sz;j++)
		{
			y=vl[i][j].fr;
			w=vl[i][j].sc;
			sg[0].ud(y,max(sg[0].qr(1,y-1),max(l,l2))+w);
		}
		for(j=sz-1;j>=0;j--)
		{
			y=vl[i][j].fr;
			w=vl[i][j].sc;
			sg[1].ud(y,max(sg[1].qr(y+1,n),l2)+w);
		}
		for(ii=0;ii<2;ii++)
		{
			mxa[i][ii]=max(mxa[i-1][ii],sg[ii].mx);
		}
	}
	z=max(mxa[n][1],mxa[n-1][0]);
	return z;
}

• 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