Submission #394439

#	Time	Username	Problem	Language	Result	Execution time	Memory
394439		shivensinha4	Teams (IOI15_teams)	C++17	0 / 100	291 ms	52512 KiB

teams

#include "bits/stdc++.h"
#include "teams.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
#define endl '\n'

struct Node {
	int pref, suf, mn, sum;
};

class SegmentTree {
	private:
		vector<Node> tree; vi raw; int n;
		int INF = 1e7;
		Node bound = {0, 0, INF, 0};
		
		Node merge(Node a, Node b) {
			if (a.mn == -INF) return b;
			if (b.mn == -INF) return a;
			
			Node ans;
			ans.sum = a.sum + b.sum;
			ans.mn = min({a.mn, b.mn, b.pref + a.suf});
			ans.suf = min(b.suf, b.sum + a.suf);
			ans.pref = min(a.pref, a.sum + b.pref);
			return ans;
		}
		
		void buildTree(int l, int r, int p) {
			if (l == r) {
				tree[p] = {raw[l], raw[l], raw[l], raw[l]};
				return;
			}
			
			int mid = (l + r) / 2;
			int c1 = 2*p+1, c2 = 2*p+2;
			buildTree(l, mid, c1); buildTree(mid+1, r, c2);
			tree[p] = merge(tree[c1], tree[c2]);
		}
		
		void update(int i, int val, int l, int r, int p) {
			if (l > i or r < i) return;
			if (l == r) {
				val = val+tree[p].sum;
				tree[p] = {val, val, val, val};
				return;
			}
			
			int mid = (l + r) / 2;
			int c1 = 2*p+1, c2 = 2*p+2;
			update(i, val, l, mid, c1); update(i, val, mid+1, r, c2);
			tree[p] = merge(tree[c1], tree[c2]);
		}
		
		Node mn(int i, int j, int l, int r, int p) {
			if (l > j or r < i) return bound;
			if (l >= i and r <= j) return tree[p];
			
			int mid = (l + r) / 2;
			int c1 = 2*p+1, c2 = 2*p+2;
			return merge(mn(i, j, l, mid, c1), mn(i, j, mid+1, r, c2));
		}
	
	public: 
		void build(vi input) {
			raw = input;
			n = raw.size();
			tree.resize(4*n);
			buildTree(0, n-1, 0);
		}
		
		int mn(int i, int j) {
			return mn(i, j, 0, n-1, 0).mn;
		}
		
		void update(int i, int val) {
			update(i, val, 0, n-1, 0);
		}
};

SegmentTree tree;
int n;

void init(int N, int A[], int B[]) {
	n = N;
	vi curr(N);
	for_(i, 0, N) {
		curr[A[i]-1]++;
		if (B[i] < N) curr[B[i]]--;
	}
	
	for_(i, 1, N) curr[i] += curr[i-1];
	tree.build(curr);
}

int can(int M, int K[]) {
	for_(i, 0, M) {
		tree.update(K[i]-1, -K[i]);
	}
	
	int ans = tree.mn(0, n-1) >= 0;
	
	for_(i, 0, M) {
		tree.update(K[i]-1, K[i]);
	}
	
	return ans;
}


// int main() {
// #ifdef mlocal
// 	freopen("teams.in", "r", stdin);
// #endif
	
// 	ios_base::sync_with_stdio(false);
// 	cin.tie(0);
	
// 	int t; cin >> t;
// 	cout << "got " << t << endl;
// 	while (t--) {
	
// 	}
// }

Compilation message (stderr)

teams.cpp: In member function 'void SegmentTree::build(vi)':
teams.cpp:71:16: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   71 |    n = raw.size();
      |        ~~~~~~~~^~

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