제출 #290420

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
290420		Berted	팀들 (IOI15_teams)	C++14	77 / 100	4030 ms	225812 KiB

teams

#include "teams.h"
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#define ll long long
#define pii pair<int, ll>
#define fst first
#define snd second

const int SZ = (1 << 20) + 5, SZ2 = 500005;

using namespace std;

struct p_node
{
	int v = 0, l = -1, r = -1;
	p_node() {}
};

int n, suf[SZ2], seg[SZ], lazy[SZ];
vector<p_node> p_seg;
vector<int> dt[SZ2];
int p_idx[SZ2];

void p_build(int idx, int L, int R)
{
	if (L < R)
	{
		int M = L + R >> 1;
		p_seg.push_back(p_node()); p_seg.push_back(p_node());
		p_seg[idx].l = p_seg.size() - 2, p_seg[idx].r = p_seg.size() - 1;
		p_build(p_seg[idx].l, L, M);
		p_build(p_seg[idx].r, M + 1, R);
	}
}

void p_upd(int idx, int odx, int L, int R, int x)
{
	if (L <= R)
	{
		if (L == x && x == R) {p_seg[idx].v = p_seg[odx].v + 1;}
		else
		{
			int M = L + R >> 1;
			p_seg.push_back(p_node());
			if (x <= M) 
			{
				p_seg[idx].l = p_seg.size() - 1;
				p_seg[idx].r = p_seg[odx].r;
				p_upd(p_seg[idx].l, p_seg[odx].l, L, M, x);
			}
			else
			{
				p_seg[idx].r = p_seg.size() - 1;
				p_seg[idx].l = p_seg[odx].l;
				p_upd(p_seg[idx].r, p_seg[odx].r, M + 1, R, x);
			}
			p_seg[idx].v = p_seg[p_seg[idx].l].v + p_seg[p_seg[idx].r].v;
		}
	}
	//cout << "UPD " << L << " " << R << " " << x << " " << p_seg[idx].v << "\n";
}

int p_qry(int idx, int L, int R, int l, int r)
{
	l = max(L, l); r = min(R, r);
	if (l <= r)
	{
		if (L == l && R == r) {return p_seg[idx].v;}
		else
		{
			int M = L + R >> 1;
			return p_qry(p_seg[idx].l, L, M, l, r) + p_qry(p_seg[idx].r, M + 1, R, l, r);
		}
	}
	return 0;
}

inline void prop(int idx, int L, int R)
{
	if (L <= R && lazy[idx] != -1)
	{
		//cout << "Propogated " << L << " " << R << " " << lazy[idx] << "\n";
		seg[idx] = p_seg[lazy[idx]].v;
		if (L < R)
		{
			lazy[2 * idx] = p_seg[lazy[idx]].l;
			lazy[2 * idx + 1] = p_seg[lazy[idx]].r;
		}
		lazy[idx] = -1;
	}
}

void bld(int idx, int L, int R)
{
	seg[idx] = 0; lazy[idx] = -1;
	if (L < R)
	{
		int M = L + R >> 1;
		bld(2 * idx, L, M);
		bld(2 * idx + 1, M + 1, R);
	}
}

void upds(int idx, int edx, int L, int R, int l, int r)
{
	l = max(L, l); r = min(R, r);
	prop(idx, L, R);
	if (l <= r)
	{
		if (L == l && R == r) 
		{
			lazy[idx] = edx; 
			prop(idx, L, R);
		}
		else
		{
			int M = L + R >> 1;
			upds(2 * idx, p_seg[edx].l, L, M, l, r);
			upds(2 * idx + 1, p_seg[edx].r, M + 1, R, l, r);
			seg[idx] = seg[2 * idx] + seg[2 * idx + 1];
		}
		//cout << "UPDS " << L << " " << R << " " << l << " " << r << " " << seg[idx] << "\n";
	}
}

void updi(int idx, int L, int R, int x, int v)
{
	prop(idx, L, R);
	if (L == x && x == R) {seg[idx] += v;}
	else
	{
		int M = L + R >> 1;
		if (x <= M) {updi(2 * idx, L, M, x, v);}
		else {updi(2 * idx + 1, M + 1, R, x, v);}
		seg[idx] = seg[2 * idx] + seg[2 * idx + 1];
	}
	//cout << "UPDI " << L << " " << R << " " << x << " " << seg[idx] << "\n";
}

int qry(int idx, int edx, int L, int R, int l, int r)
{
	l = max(L, l); r = min(r, R);
	prop(edx, L, R);
	if (l <= r)
	{
		if (L == l && R == r) 
		{
			//cout << "LEAF : " << L << " " << R << " " << p_seg[idx].v << " " << seg[edx] << "\n";
			return p_seg[idx].v - seg[edx];
		}
		else
		{
			int M = L + R >> 1;
			//cout << "QRY " << L << " " << R << " " << l << " " << r << " " << qry(p_seg[idx].l, 2 * edx, L, M, l, r) + qry(p_seg[idx].r, 2 * edx + 1, M + 1, R, l, r) << "\n";
			return qry(p_seg[idx].l, 2 * edx, L, M, l, r) + qry(p_seg[idx].r, 2 * edx + 1, M + 1, R, l, r);
		}
	}
	return 0;
}

void init(int N, int A[], int B[]) 
{
	n = N;
	for (int i = 0; i < n; i++) 
	{
		suf[A[i]]++;
		dt[A[i]].push_back(B[i]);
	}
	p_seg.push_back(p_node());
	p_idx[0] = p_seg.size() - 1;
	p_build(p_idx[0], 1, n);
	for (int i = 1; i <= n; i++)
	{
		p_idx[i] = p_idx[i - 1];
		for (auto &x : dt[i])
		{
			int nidx = p_seg.size();
			p_seg.push_back(p_node());
			p_upd(nidx, p_idx[i], 1, n, x);
			p_idx[i] = nidx;
		}
	}
	for (int i = n; i >= 0; i--) {suf[i] += suf[i + 1];}
	bld(1, 1, n);
}

int can(int M, int K[]) 
{
	//cout << "New " << M << "\n";
	upds(1, p_idx[0], 1, n, 1, n);
	sort(K, K + M); 
	for (int i = 0; i < M; i++)
	{
		//cout << "Start " << i << " " << K[i] << " " << qry(p_idx[K[i]], 1, 1, n, K[i], n) << "\n";
		if (qry(p_idx[K[i]], 1, 1, n, K[i], n) < K[i]) {return 0;}
		else
		{
			int L = K[i], R = n;
			while (L < R)
			{
				int M = L + R >> 1;
				//cout << "BINSER " << L << " " << R << "\n";
				if (qry(p_idx[K[i]], 1, 1, n, K[i], M) < K[i]) {L = M + 1;}
				else {R = M;}
			}
			//cout << i << " " << K[i] << " " << L << " " << qry(p_idx[K[i]], 1, 1, n, K[i], L - 1) << "\n";
			updi(1, 1, n, L, K[i] - qry(p_idx[K[i]], 1, 1, n, K[i], L - 1));
			upds(1, p_idx[K[i]], 1, n, K[i], L - 1);
		}
	}
	return 1;
}

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

teams.cpp: In function 'void p_build(int, int, int)':
teams.cpp:30:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |   int M = L + R >> 1;
      |           ~~^~~
teams.cpp:32:31: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   32 |   p_seg[idx].l = p_seg.size() - 2, p_seg[idx].r = p_seg.size() - 1;
      |                  ~~~~~~~~~~~~~^~~
teams.cpp:32:64: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   32 |   p_seg[idx].l = p_seg.size() - 2, p_seg[idx].r = p_seg.size() - 1;
      |                                                   ~~~~~~~~~~~~~^~~
teams.cpp: In function 'void p_upd(int, int, int, int, int)':
teams.cpp:45:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |    int M = L + R >> 1;
      |            ~~^~~
teams.cpp:49:33: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   49 |     p_seg[idx].l = p_seg.size() - 1;
      |                    ~~~~~~~~~~~~~^~~
teams.cpp:55:33: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   55 |     p_seg[idx].r = p_seg.size() - 1;
      |                    ~~~~~~~~~~~~~^~~
teams.cpp: In function 'int p_qry(int, int, int, int, int)':
teams.cpp:73:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |    int M = L + R >> 1;
      |            ~~^~~
teams.cpp: In function 'void bld(int, int, int)':
teams.cpp:100:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |   int M = L + R >> 1;
      |           ~~^~~
teams.cpp: In function 'void upds(int, int, int, int, int, int)':
teams.cpp:119:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  119 |    int M = L + R >> 1;
      |            ~~^~~
teams.cpp: In function 'void updi(int, int, int, int, int)':
teams.cpp:134:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  134 |   int M = L + R >> 1;
      |           ~~^~~
teams.cpp: In function 'int qry(int, int, int, int, int, int)':
teams.cpp:155:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  155 |    int M = L + R >> 1;
      |            ~~^~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:172:26: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  172 |  p_idx[0] = p_seg.size() - 1;
      |             ~~~~~~~~~~~~~^~~
teams.cpp:179:25: warning: conversion from 'std::vector<p_node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  179 |    int nidx = p_seg.size();
      |               ~~~~~~~~~~^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:203:9: warning: declaration of 'int M' shadows a parameter [-Wshadow]
  203 |     int M = L + R >> 1;
      |         ^
teams.cpp:189:13: note: shadowed declaration is here
  189 | int can(int M, int K[])
      |         ~~~~^
teams.cpp:203:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  203 |     int M = L + R >> 1;
      |             ~~^~~

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