Submission #90814

#	Time	Username	Problem	Language	Result	Execution time	Memory
90814		YottaByte	Schools (IZhO13_school)	C++14	25 / 100	416 ms	27088 KiB

school

#include <bits/stdc++.h>

#define pb push_back
#define mk make_pair
#define fr first
#define sc second

using namespace std;

const int N = 3e5 + 5;

int n, x, y, must[N * 4];

pair <int, int> t[N * 4];

pair <int, int> a[N];

long long ans;

void push(int v, int tl, int tr)
{
	t[v].fr += must[v];
	
	if (tl != tr)
	{
		must[v + v] += must[v];
		must[v + v + 1] += must[v];
	}
	
	must[v] = 0;
}

void upd (int l, int r, int val, int v = 1, int tl = 1, int tr = n)
{
	push(v, tl, tr);
	
	if (tl > r || l > tr) return;
	
	if (l <= tl && tr <= r)
	{
		must[v] += val;
		push(v, tl, tr);
		return ;
	}
	int tm = (tl + tr) >> 1;
	upd(l, r, val, v + v, tl, tm);
	upd(l, r, val, v + v + 1, tm + 1, tr);
		
	t[v] = max( t[v + v], t[v + v + 1] );
}
void build (int v = 1, int tl = 1, int tr = n)
{
	if(tl == tr)
	{
		if (tl <= x)
			t[v] = mk( -a[tl].fr + a[tl].sc + a[x + 1].fr, tl );
		else
			t[v] = mk( a[tl].sc, tl );
	}
	else
	{
		int tm = (tl + tr) >> 1;
		build( v + v, tl, tm );
		build( v + v + 1, tm + 1, tr );
		t[v] = max(t[v + v], t[v + v + 1]);
	}
}
set <int> st;

main()
{
	cin >> n >> x >> y;
	
	for (int i = 1; i <= n; i++)
	{
		scanf("%d%d", &a[i].fr, &a[i].sc);
	}
	sort( a + 1, a + n + 1, greater < pair <int, int> >() );
	
	for (int i = 1; i <= x; i++)
		ans += a[i].fr;
	for (int i = x + 1; i <= n; i++)
		st.insert(i);
		
	build();
	
	while(y--)
	{
		if ( st.count( t[1].sc ) )
		{
			int val = t[1].fr, ind = t[1].sc;
			
			ans += t[1].fr;
			
			upd( 1, x, -a[*st.begin()].fr );
			upd( ind, ind, -1e9 - 7 );
			
			st.erase(ind );
			
			if (!st.empty())
				upd( 1, x, +a[*st.begin()].fr );
		}
		else
		{
			int val = t[1].fr, ind = t[1].sc;
			
			ans += t[1].fr;
			
			upd( 1, x, -a[*st.begin()].fr );
			
			upd( *st.begin(), *st.begin(), -1e9 - 7 );
			st.erase(st.begin());
			
			if (!st.empty())
				upd( 1, x, +a[*st.begin()].fr );
				
			upd( ind, ind, -1e9 - 7 );
		}
	}
	cout << ans << endl;
}
/**
5 3 2
41 36
47 16
27 2
29 4
33 30


**/

Compilation message (stderr)

school.cpp:70:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
school.cpp: In function 'int main()':
school.cpp:91:8: warning: unused variable 'val' [-Wunused-variable]
    int val = t[1].fr, ind = t[1].sc;
        ^~~
school.cpp:105:8: warning: unused variable 'val' [-Wunused-variable]
    int val = t[1].fr, ind = t[1].sc;
        ^~~
school.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a[i].fr, &a[i].sc);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 100