제출 #1029469

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1029469		Dan4Life	팀들 (IOI15_teams)	C++17	77 / 100	4058 ms	171580 KiB

teams

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ar2 = array<int,2>;
const int mxN = (int)5e5+10;
const int mxM = (int)2e5+10;
ar2 v[mxN]; int n;
multiset<int> S;
const int B = sqrt(mxN);
const int mxLg = __lg(mxN)+1;
const int mxSeg = mxN*4*mxLg;
int a[mxN], b[mxN];
int seg[mxSeg], L[mxSeg], R[mxSeg], root[mxSeg];
int segNodes = 1;

int newChild(int p, int v){
	int np = ++segNodes;
	seg[np] = seg[p]+v;
	L[np]=R[np]=0;
	return np;
}

int newParent(int lp, int rp){
	int np = ++segNodes;
	L[np] = lp; R[np] = rp;
	seg[np] = seg[lp]+seg[rp];
	return np;
}

int upd(int x, int v, int p, int l=1, int r=n){
	if(!p) return p;
	if(l==r) return newChild(p,v);
	int mid = (l+r)/2;
	if(!L[p]) L[p]=++segNodes;
	if(!R[p]) R[p]=++segNodes;
	if(x<=mid) return newParent(upd(x,v,L[p],l,mid),R[p]);
	else return newParent(L[p],upd(x,v,R[p],mid+1,r));
}

int query(int i, int j, int p, int l=1, int r=n){
	if(!p or i>r or j<l or i>j) return 0;
	if(i<=l and r<=j) return seg[p];
	int mid = (l+r)/2;
	return query(i,j,L[p],l,mid)+query(i,j,R[p],mid+1,r);
}

void init(int N, int A[], int B[]) {
	n = N;
	for(int i = 0; i < n; i++) a[i]=A[i],b[i]=B[i];
	for(int i = 0; i < n; i++) v[i]={a[i],b[i]};
    sort(v,v+n,[&](ar2 x, ar2 y){ return x[1]>y[1]; }); 
    int j = 0;
    root[n+1] = 1;
    for(int i = n; i>=1; i--){
		root[i] = root[i+1];
		while(j<n and v[j][1]==i)
			root[i]=upd(v[j][0],1,root[i]), j++;
	}
}

int dp[B+10];
int can(int m, int a[]) {
	sort(a,a+m); 
	if(m>=B){
		reverse(a,a+m);
		int j = 0; S.clear();
		for(int i = 0; i < m; i++){
			int x = a[i];
			while(j<n and v[j][1]>=a[i]) 
				S.insert(v[j][0]), j++;
			while(x--){
				auto itr = S.upper_bound(a[i]);
				if(itr==begin(S)) return 0;
				S.erase(--itr);
			}
		}
		return 1;
	}
	for(int i = 0; i < m; i++){
		dp[i] = query(1,a[i],root[a[i]]);
		for(int j = 0; j < i; j++)
			dp[i] = min(dp[i], dp[j]+query(a[j]+1,a[i],root[a[i]]));
		dp[i]-=a[i];
		if(dp[i]<0) return 0;
	}
	return 1;
}

컴파일 시 표준 에러 (stderr) 메시지

teams.cpp:11:19: warning: conversion from 'double' to 'int' changes value from '7.0711385221900446e+2' to '707' [-Wfloat-conversion]
   11 | const int B = sqrt(mxN);
      |               ~~~~^~~~~
teams.cpp: In function 'int newChild(int, int)':
teams.cpp:18:25: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   18 | int newChild(int p, int v){
      |                     ~~~~^
teams.cpp:9:5: note: shadowed declaration is here
    9 | ar2 v[mxN]; int n;
      |     ^
teams.cpp: In function 'int upd(int, int, int, int, int)':
teams.cpp:32:20: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   32 | int upd(int x, int v, int p, int l=1, int r=n){
      |                ~~~~^
teams.cpp:9:5: note: shadowed declaration is here
    9 | ar2 v[mxN]; int n;
      |     ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:49:31: warning: declaration of 'B' shadows a global declaration [-Wshadow]
   49 | void init(int N, int A[], int B[]) {
      |                           ~~~~^~~
teams.cpp:11:11: note: shadowed declaration is here
   11 | const int B = sqrt(mxN);
      |           ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:64:20: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   64 | int can(int m, int a[]) {
      |                ~~~~^~~
teams.cpp:14:5: note: shadowed declaration is here
   14 | int a[mxN], b[mxN];
      |     ^

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 0 / 23