Submission #782768

#	Time	Username	Problem	Language	Result	Execution time	Memory
782768		fatemetmhr	Teams (IOI15_teams)	C++17	0 / 100	4046 ms	77648 KiB

teams

//  ~ Be Name Khoda ~  //

#include "teams.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  2e6   + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const int lg    =  21;
const ll  inf   =  1e18;

int n;
vector <int> av[maxn5];
vector <pair<int, int>> all;

namespace seg{

	int pt[lg], seg[lg][maxn5], ptl[maxnt], ptr[maxnt];

	void build(int l, int r, int v, int h){
		if(r - l == 1){
			ptl[v] = pt[h];
			for(auto u : av[l])
				seg[h][pt[h]++] = u;
			ptr[v] = pt[h];
			sort(seg[h] + ptl[v], seg[h] + ptr[v]);
			return;
		}
		int mid = (l + r) >> 1;
		build(l, mid, v * 2, h + 1);
		build(mid, r, v * 2 + 1, h + 1);
		ptl[v] = pt[h];
		int pt1 = ptl[v * 2], pt2 = ptl[v * 2 + 1];
		while(pt1 < ptr[v * 2] || pt2 < ptr[v * 2 + 1]){
			if(pt1 < ptr[v * 2] && (pt2 == ptr[v * 2 + 1] || seg[h + 1][pt1] < seg[h + 1][pt2]))
				seg[h][pt[h]++] = seg[h + 1][pt1++];
			else
				seg[h][pt[h]++] = seg[h + 1][pt2++];
		}
		ptr[v] = pt[h];
	}

	int get(int l, int r, int lq, int rq, int lq2, int rq2, int v, int h){
		int ans = 0;
		for(auto [u, v] : all) if(lq <= u && u < rq && lq2 <= v && v < rq2)
			ans++;
		return ans;
		if(rq <= l || r <= lq)
			return 0;
		if(lq <= l && r <= rq){
			int x = lower_bound(seg[h] + ptl[v], seg[h] + ptr[v], lq2) - seg[h];
			int y = lower_bound(seg[h] + ptl[v], seg[h] + ptr[v], rq2) - seg[h];
			return y - x;
		}
		int mid = (l + r) >> 1;
		return get(l, mid, lq, rq, lq2, rq2, v * 2, h + 1) + get(mid, r, lq, rq, lq2, rq2, v * 2 + 1, h + 1);
	}
}

void init(int N, int A[], int B[]) {
	n = N;
	for(int i = 0; i < n; i++){
		all.pb({A[i], B[i]});
		av[A[i]].pb(B[i]);
	}
	seg::build(0, n + 1, 1, 0);
}

int can(int m, int k[]) {
	sort(k, k + m);
	int rem = seg::get(0, n + 1, 0, k[0] + 1, k[0], n + 1, 1, 0), used = 0;
	for(int i = 0; i < m; i++){
		if(rem - used < k[i])
			return false;
		if(i == m - 1)
			return true;
		used += k[i];
		int er = seg::get(0, n + 1, 0, k[i] + 1, k[i], k[i + 1], 1, 0);
		rem -= er;
		used = max(0, used - er);
		//cout << "hey " << i << ' ' << k[i] << ' ' << rem << ' ' << er << ' ' << used << ' ' << k[i + 1] << endl;
		rem += seg::get(0, n + 1, k[i] + 1, k[i + 1] + 1, k[i + 1], n + 1, 1, 0);
		//cout << "ok " << rem << endl;
	}
	return true;
}

Compilation message (stderr)

teams.cpp: In function 'int seg::get(int, int, int, int, int, int, int, int)':
teams.cpp:60:16: warning: declaration of 'auto v' shadows a parameter [-Wshadow]
   60 |   for(auto [u, v] : all) if(lq <= u && u < rq && lq2 <= v && v < rq2)
      |                ^
teams.cpp:58:62: note: shadowed declaration is here
   58 |  int get(int l, int r, int lq, int rq, int lq2, int rq2, int v, int h){
      |                                                          ~~~~^
teams.cpp:66:63: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   66 |    int x = lower_bound(seg[h] + ptl[v], seg[h] + ptr[v], lq2) - seg[h];
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
teams.cpp:67:63: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   67 |    int y = lower_bound(seg[h] + ptl[v], seg[h] + ptr[v], rq2) - seg[h];
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~

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