oj.uz

답안 #119787

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
119787 2019-06-22T10:07:55 Z MvC 팀들 (IOI15_teams) C++11
0 / 100
 1081 ms 154728 KB 
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
#include "teams.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=5e5+50;
const int mod=1e9+7;
using namespace std;
int n,i,nr[nmax],st[10*20*nmax],lch[10*20*nmax],rch[10*20*nmax],q,t,x,y,nds,r,rt[nmax],nd[nmax],m,s,j,k[nmax];
vector<int>a[nmax];
int nlf(int x)
{
	int p=++nds;
	lch[p]=rch[p]=0;
	st[p]=x;
	return p;
}
int npr(int l,int r)
{
	int p=++nds;
	lch[p]=l,rch[p]=r;
	st[p]=st[l]+st[r];
	return p;
}
int upd(int nod,int l,int r,int p)
{
	if(l==r)return nlf(1);
	int mid=(l+r)/2;
	if(p<=mid)return npr(upd(lch[nod],l,mid,p),rch[nod]);
	else return npr(lch[nod],upd(rch[nod],mid+1,r,p));
}
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(lch[nod],l,mid,tl,tr);
	if(tr>mid)v+=qry(rch[nod],mid+1,r,tl,tr);
	return v;
}
void init(int N,int A[],int B[])
{
	n=N;
	for(i=1;i<=n;i++)
	{
		x=A[i-1],y=B[i-1];
		a[x].pb(y);
	}
	for(i=1;i<=n;i++)
	{
		for(j=0;j<a[i].size();j++)
		{
			nr[a[i][j]]++;
			rt[++r]=upd(rt[r-1],1,n,a[i][j]);
		}
		nd[i]=rt[r];
	}
}
int can(int M,int K[])
{
	m=M;
	for(i=1;i<=m;i++)k[i]=K[i-1];
	sort(k+1,k+m+1);
	s=0;
	for(i=1;i<=m;i++)
	{
		s+=k[i];
		if(!(qry(nd[k[i]],1,n,k[i],n)>=k[i] && qry(nd[k[i]],1,n,k[1],n)>=s))break;
	}
	if(i==m+1)return 1;
	return 0;
}
/*int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>x>>y;
		a[x].pb(y);
	}
	for(i=1;i<=n;i++)
	{
		for(j=0;j<a[i].size();j++)
		{
			nr[a[i][j]]++;
			rt[++r]=upd(rt[r-1],1,n,a[i][j]);
		}
		nd[i]=rt[r];
	}
	cin>>q;
	while(q--)
	{
		cin>>m;
		for(i=1;i<=m;i++)cin>>k[i];
		sort(k+1,k+m+1);
		s=0;
		for(i=1;i<=m;i++)
		{
			s+=k[i];
			if(!(qry(nd[k[i]],1,n,k[i],n)>=k[i] && qry(nd[k[i]],1,n,k[1],n)>=s))break;
		}
		if(i==m+1)cout<<1<<endl;
		else cout<<0<<endl;
	}
    return 0;
}*/

Compilation message

teams.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
teams.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")
 
teams.cpp: In function 'int nlf(int)':
teams.cpp:24:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 int nlf(int x)
              ^
teams.cpp:22:69: note: shadowed declaration is here
 int n,i,nr[nmax],st[10*20*nmax],lch[10*20*nmax],rch[10*20*nmax],q,t,x,y,nds,r,rt[nmax],nd[nmax],m,s,j,k[nmax];
                                                                     ^
teams.cpp: In function 'int npr(int, int)':
teams.cpp:31:20: warning: declaration of 'r' shadows a global declaration [-Wshadow]
 int npr(int l,int r)
                    ^
teams.cpp:22:77: note: shadowed declaration is here
 int n,i,nr[nmax],st[10*20*nmax],lch[10*20*nmax],rch[10*20*nmax],q,t,x,y,nds,r,rt[nmax],nd[nmax],m,s,j,k[nmax];
                                                                             ^
teams.cpp: In function 'int upd(int, int, int, int)':
teams.cpp:38:34: warning: declaration of 'r' shadows a global declaration [-Wshadow]
 int upd(int nod,int l,int r,int p)
                                  ^
teams.cpp:22:77: note: shadowed declaration is here
 int n,i,nr[nmax],st[10*20*nmax],lch[10*20*nmax],rch[10*20*nmax],q,t,x,y,nds,r,rt[nmax],nd[nmax],m,s,j,k[nmax];
                                                                             ^
teams.cpp: In function 'int qry(int, int, int, int, int)':
teams.cpp:45:42: warning: declaration of 'r' shadows a global declaration [-Wshadow]
 int qry(int nod,int l,int r,int tl,int tr)
                                          ^
teams.cpp:22:77: note: shadowed declaration is here
 int n,i,nr[nmax],st[10*20*nmax],lch[10*20*nmax],rch[10*20*nmax],q,t,x,y,nds,r,rt[nmax],nd[nmax],m,s,j,k[nmax];
                                                                             ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:65:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<a[i].size();j++)
           ~^~~~~~~~~~~~
teams.cpp:68:7: warning: operation on 'r' may be undefined [-Wsequence-point]
    rt[++r]=upd(rt[r-1],1,n,a[i][j]);
       ^~~

Subtask #1
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 12160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 36732 KB Output is correct
2 Correct 92 ms 36632 KB Output is correct
3 Correct 94 ms 36600 KB Output is correct
4 Correct 91 ms 37496 KB Output is correct
5 Incorrect 40 ms 35064 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 37048 KB Output is correct
2 Correct 88 ms 36984 KB Output is correct
3 Incorrect 221 ms 39996 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 684 ms 148856 KB Output is correct
2 Correct 700 ms 148888 KB Output is correct
3 Incorrect 1081 ms 154728 KB Output isn't correct
4 Halted 0 ms 0 KB -