oj.uz

답안 #117069

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
117069 2019-06-14T15:14:14 Z MvC 모임들 (IOI18_meetings) C++11
36 / 100
 1147 ms 239964 KB 
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
//#include "meetings.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const ll nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int n,q,i,j,x,y,lst,t,st[4*nmax];
ll h[nmax],p[5050][5050],s[5050][5050],mx;
vector<pair<int,int> >a[nmax],b[nmax];
vector<ll>rs;
void upd(int nod,int l,int r,int p,int v)
{
	if(l==r)
	{
		st[nod]=max(v,st[nod]);
		return;
	}
	int mid=(l+r)/2;
	if(p<=mid)upd(2*nod,l,mid,p,v);
	else upd(2*nod+1,mid+1,r,p,v);
	st[nod]=max(st[2*nod],st[2*nod+1]);
}
int qry(int nod,int l,int r,int tl,int tr)
{
	if(tr<l || tl>r)return 0;
	if(tl<=l && r<=tr)return st[nod];
	int mid=(l+r)/2;
	int v=0;
	if(tl<=mid)v=qry(2*nod,l,mid,tl,tr);
	if(tr>mid)v=max(v,qry(2*nod+1,mid+1,r,tl,tr));
	return v;
}
vector<ll> minimum_costs(vector<int>H,vector<int>L,vector<int>R)
{
	n=H.size(),q=L.size();
	for(i=1;i<=n;i++)h[i]=H[i-1];
	h[n+1]=h[0]=2;
	for(i=0;i<q;i++)
	{
		x=L[i],y=R[i];
		x++,y++;
		if(x>y)swap(x,y);
		a[y].pb(mkp(x,i));
		b[x].pb(mkp(y,i));
	}
	rs.resize(q);
	if(n<=5000 && q<=5000)
	{
		for(i=0;i<q;i++)rs[i]=llinf;
		for(i=1;i<=n;i++)
		{
			mx=0;
			for(j=i;j<=n;j++)
			{
				mx=max(mx,h[j]);
				p[i][j]=p[i][j-1]+mx;
			}
			mx=0;
			for(j=i-1;j>=1;j--)
			{
				mx=max(mx,h[j]);
				s[i][j]=s[i][j+1]+mx;
			}
		}
		for(i=1;i<=n;i++)
		{
			for(j=0;j<a[i].size();j++)
			{
				x=a[i][j].fr,y=i;
				for(t=x;t<=y;t++)
				{
					rs[a[i][j].sc]=min(rs[a[i][j].sc],p[t][y]+s[t][x]);
				}
			}
		}
		return rs;
	}
	for(i=1;i<=n;i++)
	{
		if(h[i]==2)lst=i;
		if(lst!=i && h[i+1]==2)upd(1,1,n,lst+1,i-lst);
		for(j=0;j<a[i].size();j++)rs[a[i][j].sc]=qry(1,1,n,a[i][j].fr,i);
	}
	lst=0;
	for(i=1;i<=n;i++)
	{
		if(h[i]==2)lst=i;
		for(j=0;j<a[i].size();j++)rs[a[i][j].sc]=max(rs[a[i][j].sc],1LL*i-1LL*max(lst,a[i][j].fr-1));
	}
	lst=n+1;
	for(i=n;i>=1;i--)
	{
		if(h[i]==2)lst=i;
		for(j=0;j<b[i].size();j++)rs[b[i][j].sc]=max(rs[b[i][j].sc],1LL*min(lst,b[i][j].fr+1)-1LL*i);
	}
	for(i=1;i<=n;i++)
	{
		for(j=0;j<a[i].size();j++)
		{
			rs[a[i][j].sc]=rs[a[i][j].sc]+(i-a[i][j].fr+1-rs[a[i][j].sc])*2;
		}
	}
	return rs;
}

Compilation message

meetings.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
meetings.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")
 
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:82:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=0;j<a[i].size();j++)
            ~^~~~~~~~~~~~
meetings.cpp:97:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<a[i].size();j++)rs[a[i][j].sc]=qry(1,1,n,a[i][j].fr,i);
           ~^~~~~~~~~~~~
meetings.cpp:103:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<a[i].size();j++)rs[a[i][j].sc]=max(rs[a[i][j].sc],1LL*i-1LL*max(lst,a[i][j].fr-1));
           ~^~~~~~~~~~~~
meetings.cpp:109:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<b[i].size();j++)rs[b[i][j].sc]=max(rs[b[i][j].sc],1LL*min(lst,b[i][j].fr+1)-1LL*i);
           ~^~~~~~~~~~~~
meetings.cpp:113:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<a[i].size();j++)
           ~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5084 KB Output is correct
2 Correct 113 ms 99780 KB Output is correct
3 Correct 115 ms 99840 KB Output is correct
4 Correct 113 ms 99832 KB Output is correct
5 Correct 114 ms 99752 KB Output is correct
6 Correct 113 ms 99804 KB Output is correct
7 Correct 112 ms 99832 KB Output is correct
8 Correct 113 ms 99788 KB Output is correct
9 Correct 113 ms 99844 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5084 KB Output is correct
2 Correct 113 ms 99780 KB Output is correct
3 Correct 115 ms 99840 KB Output is correct
4 Correct 113 ms 99832 KB Output is correct
5 Correct 114 ms 99752 KB Output is correct
6 Correct 113 ms 99804 KB Output is correct
7 Correct 112 ms 99832 KB Output is correct
8 Correct 113 ms 99788 KB Output is correct
9 Correct 113 ms 99844 KB Output is correct
10 Correct 534 ms 239872 KB Output is correct
11 Correct 1141 ms 239784 KB Output is correct
12 Correct 539 ms 239876 KB Output is correct
13 Correct 1147 ms 239832 KB Output is correct
14 Correct 539 ms 239964 KB Output is correct
15 Correct 581 ms 239944 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 52 ms 8284 KB Output is correct
3 Correct 179 ms 14776 KB Output is correct
4 Correct 171 ms 14588 KB Output is correct
5 Correct 179 ms 17072 KB Output is correct
6 Correct 176 ms 16404 KB Output is correct
7 Correct 163 ms 13776 KB Output is correct

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 52 ms 8284 KB Output is correct
3 Correct 179 ms 14776 KB Output is correct
4 Correct 171 ms 14588 KB Output is correct
5 Correct 179 ms 17072 KB Output is correct
6 Correct 176 ms 16404 KB Output is correct
7 Correct 163 ms 13776 KB Output is correct
8 Incorrect 172 ms 14772 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5084 KB Output is correct
2 Correct 113 ms 99780 KB Output is correct
3 Correct 115 ms 99840 KB Output is correct
4 Correct 113 ms 99832 KB Output is correct
5 Correct 114 ms 99752 KB Output is correct
6 Correct 113 ms 99804 KB Output is correct
7 Correct 112 ms 99832 KB Output is correct
8 Correct 113 ms 99788 KB Output is correct
9 Correct 113 ms 99844 KB Output is correct
10 Correct 534 ms 239872 KB Output is correct
11 Correct 1141 ms 239784 KB Output is correct
12 Correct 539 ms 239876 KB Output is correct
13 Correct 1147 ms 239832 KB Output is correct
14 Correct 539 ms 239964 KB Output is correct
15 Correct 581 ms 239944 KB Output is correct
16 Correct 7 ms 5112 KB Output is correct
17 Correct 52 ms 8284 KB Output is correct
18 Correct 179 ms 14776 KB Output is correct
19 Correct 171 ms 14588 KB Output is correct
20 Correct 179 ms 17072 KB Output is correct
21 Correct 176 ms 16404 KB Output is correct
22 Correct 163 ms 13776 KB Output is correct
23 Incorrect 172 ms 14772 KB Output isn't correct
24 Halted 0 ms 0 KB -