제출 #1032964

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1032964		Dan4Life	팀들 (IOI15_teams)	C++17	34 / 100	4022 ms	113000 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 = 300;
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;
 
template<class T> using V = vector<T>;
using pi = pair<int,int>;
 
template<class T, int SZ> class OffBIT2D {
	bool initialized = 0;
	// V<int> all_y;
	vector<int> all_y[SZ];
	// int y_cnt[SZ]{};
	// int y_start[SZ]{};
	// V<T> bit;
	V<T> bit[SZ];
	int rank_of_y(int x, int y) { // get rank of y in distinct y-values for x
		// int l = y_start[x], r = y_start[x]+y_cnt[x];
		// return upper_bound(begin(all_y)+l,begin(all_y)+r,y)-begin(all_y)-l;
		return upper_bound(begin(all_y[x]),end(all_y[x]), y)-begin(all_y[x]);
	}
public:
	// all updates {x,y} must satisfy x in (0, SZ), no restrictions on y
	void init(V<pair<int,int>> updates) {
		assert(!initialized);
		initialized = true;
		sort(begin(updates), end(updates),[](const pi& a, const pi& b) { 
			return a.second < b.second; 
		});
		vector<int> y_cnt(SZ);
		for (auto [x, y]: updates) // push to log(N) different BITs
			for (; x < SZ; x += x&-x) {
				++y_cnt[x];
			}
		for (int x = 0; x < SZ; ++x) {
			all_y[x].reserve(y_cnt[x]);
			bit[x].resize(y_cnt[x]);
		}
		for (auto [x, y]: updates) {
			for (; x < SZ; x += x&-x) {
				all_y[x].push_back(y);
			}
		}
	}
	void upd(int x, int _y, T t) {
		assert(initialized);
		for (; x < SZ; x += x&-x)
			for (int y = rank_of_y(x,_y); y <= sz(all_y[x]); y += y&-y) 
				bit[x][y-1] += t;
	}
	T sum(int x, int _y) {
		assert(initialized);
		T res = 0;
		for (; x; x -= x&-x)
			for (int y = rank_of_y(x,_y); y; y -= y&-y)
				res += bit[x][y-1];
		return res;
	}
	T sum(int xl, int xr, int yl, int yr) { 
		return sum(xr,yr)-sum(xl-1,yr)-sum(xr,yl-1)+sum(xl-1,yl-1); 
	}
};
OffBIT2D<int,mxN> fen2d;
 
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]};
	V<pi> updates(N);
	for(int i = 0; i < n; i++) updates[i]={a[i],b[i]};
	fen2d.init(updates); for(auto [x,y] : updates) fen2d.upd(x,y,1);
    sort(v,v+n,[&](ar2 x, ar2 y){ return x[1]>y[1]; }); 
}
 
int dp[B+10];
int f(int j, int i, int a[]){
	return dp[j]+fen2d.sum(a[j]+1,a[i],a[i],n);
}
 
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;
	}
	deque<int> dq; dq.clear();
	for(int i = 0; i < m; i++){
		dp[i] = fen2d.sum(1,a[i],a[i],n);
		while(sz(dq)>1 and f(end(dp)[-2],i,a) < f(end(dp)[-1],i,a)) dq.pop_back();
		for(auto j : dq) dp[i] = min(dp[i], f(j,i,a));
		dp[i]-=a[i];
		if(dp[i]<0) return 0;
		dq.pb(i);
	}
	return 1;
}

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

teams.cpp: In lambda function:
teams.cpp:39:63: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   39 |   sort(begin(updates), end(updates),[](const pi& a, const pi& b) {
      |                                                     ~~~~~~~~~~^
teams.cpp:14:13: note: shadowed declaration is here
   14 | int a[mxN], b[mxN];
      |             ^
teams.cpp:39:50: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   39 |   sort(begin(updates), end(updates),[](const pi& a, const pi& b) {
      |                                        ~~~~~~~~~~^
teams.cpp:14:5: note: shadowed declaration is here
   14 | int a[mxN], b[mxN];
      |     ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:77:31: warning: declaration of 'B' shadows a global declaration [-Wshadow]
   77 | void init(int N, int A[], int B[]) {
      |                           ~~~~^~~
teams.cpp:11:11: note: shadowed declaration is here
   11 | const int B = 300;
      |           ^
teams.cpp: In function 'int f(int, int, int*)':
teams.cpp:88:25: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   88 | int f(int j, int i, int a[]){
      |                     ~~~~^~~
teams.cpp:14:5: note: shadowed declaration is here
   14 | int a[mxN], b[mxN];
      |     ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:92:20: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   92 | int can(int m, int a[]) {
      |                ~~~~^~~
teams.cpp:14:5: note: shadowed declaration is here
   14 | int a[mxN], b[mxN];
      |     ^
teams.cpp: In instantiation of 'void OffBIT2D<T, SZ>::init(V<std::pair<int, int> >) [with T = int; int SZ = 500010; V<std::pair<int, int> > = std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >]':
teams.cpp:83:20:   required from here
teams.cpp:39:63: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   39 |   sort(begin(updates), end(updates),[](const pi& a, const pi& b) {
      |                                                     ~~~~~~~~~~^
teams.cpp:14:13: note: shadowed declaration is here
   14 | int a[mxN], b[mxN];
      |             ^
teams.cpp:39:50: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   39 |   sort(begin(updates), end(updates),[](const pi& a, const pi& b) {
      |                                        ~~~~~~~~~~^
teams.cpp:14:5: note: shadowed declaration is here
   14 | int a[mxN], b[mxN];
      |     ^
teams.cpp: In instantiation of 'int OffBIT2D<T, SZ>::rank_of_y(int, int) [with T = int; int SZ = 500010]':
teams.cpp:60:17:   required from 'void OffBIT2D<T, SZ>::upd(int, int, T) [with T = int; int SZ = 500010]'
teams.cpp:83:64:   required from here
teams.cpp:32:55: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   32 |   return upper_bound(begin(all_y[x]),end(all_y[x]), y)-begin(all_y[x]);
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

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