Submission #1063659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063659		nishkarsh	Teams (IOI15_teams)	C++14	0 / 100	663 ms	153220 KiB

teams

#include <bits/stdc++.h>
#define ll long long
#define vt vector
#define pb push_back
using namespace std;

int fastexp(int b, int e, int mod){
	int ans = 1;
	while(e){
		if(e&1) ans = (1ll*ans*b)%mod;
		b = (1ll*b*b)%mod;
		e >>= 1;
	}
	return ans;
}

const int N = 5e5+1;
const int mod = 998244353;
const ll INFLL = 1e18;
const int INF = 2e9;
const int logn = 20;

struct pers_segtree_node{
	int lt,rt,val;
};

int pers_segtree_nodecnt = 0;
pers_segtree_node pers_segtree[N*logn];
int update(int node, int i, int j, int ind){
	int nw_node = ++pers_segtree_nodecnt;
	pers_segtree[nw_node] = pers_segtree[node];
	pers_segtree[nw_node].val++;

	if(i == j) return nw_node;

	int mid = (i+j) / 2;
	if(ind <= mid) pers_segtree[nw_node].lt = update(pers_segtree[node].lt, i, mid, ind);
	else pers_segtree[nw_node].rt = update(pers_segtree[node].rt, mid+1, j, ind);
	return nw_node;
}

struct my_segtree_node{
	int curr, latest, last_exhausted;
};

int my_segtree_nodecnt;
my_segtree_node my_segtree[4*N];

void query(int node, int i, int j, int l, int r, int pers_segtree_node_num, int tim, int &val){
	if(! my_segtree[node].last_exhausted) my_segtree[node].last_exhausted = 1;
	if(val == 0 || pers_segtree_node_num == 0 || i > r || l > j || i > j || l > r) return;
	if(i >= l && j <= r){
		int left = pers_segtree[pers_segtree_node_num].val - pers_segtree[my_segtree[node].latest].val - my_segtree[node].curr;
		if(val >= left){
			val -= left;
			my_segtree[node].latest = pers_segtree_node_num;
			my_segtree[node].last_exhausted = tim;
			my_segtree[node].curr = 0;
			return;
		}
		else my_segtree[node].curr += val;
	}

	if(i == j) return;

	int mid = (i+j) / 2;

	if(my_segtree[2*node].last_exhausted < my_segtree[node].last_exhausted){
		my_segtree[2*node].last_exhausted = my_segtree[node].last_exhausted;
		my_segtree[2*node].curr = 0;
		my_segtree[2*node].latest = pers_segtree[my_segtree[node].latest].lt;
	}

	query(2*node, i, mid, l, r, pers_segtree[pers_segtree_node_num].lt, tim, val);

	if(my_segtree[2*node+1].last_exhausted < my_segtree[node].last_exhausted){
		my_segtree[2*node+1].last_exhausted = my_segtree[node].last_exhausted;
		my_segtree[2*node+1].curr = 0;
		my_segtree[2*node+1].latest = pers_segtree[my_segtree[node].latest].rt;
	}

	query(2*node+1, mid+1, j, l, r, pers_segtree[pers_segtree_node_num].rt, tim, val);
}

void clear_my_segtree(int node, int i, int j){
	if(my_segtree[node].curr == 0 && my_segtree[node].latest == 0 && my_segtree[node].last_exhausted == 0) return;
	my_segtree[node] = {0,0,0};
	if(i==j) return;
	int mid = (i+j)/2;
	clear_my_segtree(2*node,i,mid);
	clear_my_segtree(2*node + 1,mid+1,j);
}

int times[N];
int n;

void init(int N, int *A, int *B){
	n = N;
	vt<vt<int>> ranges(n+1);
	for(int i = 0; i < n; i++) ranges[A[i]].pb(B[i]);

	for(int i = 1; i <= n; i++){
		times[i] = times[i-1];
		for(int j : ranges[i]) times[i] = update(times[i], 1, N, j);
	}
}

bool can(int M, int *K){
	sort(K,K+M);
	for(int i = 0; i < M; i++){
		int temp_val = K[i];
		query(1,1,n,K[i],n,times[K[i]],i+2,temp_val);
		if(temp_val > 0){
			clear_my_segtree(1,1,n);
			return false;
		}
	}
	clear_my_segtree(1,1,n);
	return true;
}

void solve(){
	int n;
	cin >> n;
	int A[n],B[n];
	for(int i = 0; i < n; i++) cin >> A[i] >> B[i];
	init(n,A,B);
	int q,k;
	cin >> q;
	while(q--){
		cin >> k;
		int temp[k];
		for(int i = 0; i < k; i++) cin >> temp[i];
		cout << can(k,temp) << "\n";
	}
}

// int main()
// {
// 	ios_base::sync_with_stdio(false);
// 	cin.tie(NULL);

// 	int t = 1;
// 	// cin >> t;
// 	while(t--){
// 		solve();
// 	}

// 	return 0;
// }

Compilation message (stderr)

teams.cpp: In function 'int fastexp(int, int, int)':
teams.cpp:10:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   10 |   if(e&1) ans = (1ll*ans*b)%mod;
      |                 ~~~~~~~~~~~^~~~
teams.cpp:11:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   11 |   b = (1ll*b*b)%mod;
      |       ~~~~~~~~~^~~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:97:15: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   97 | void init(int N, int *A, int *B){
      |           ~~~~^
teams.cpp:17:11: note: shadowed declaration is here
   17 | const int N = 5e5+1;
      |           ^
teams.cpp: In function 'void solve()':
teams.cpp:123:6: warning: declaration of 'n' shadows a global declaration [-Wshadow]
  123 |  int n;
      |      ^
teams.cpp:95:5: note: shadowed declaration is here
   95 | int n;
      |     ^

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