| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1043904 |
2024-08-05T03:24:26 Z |
vjudge1 |
Schools (IZhO13_school) |
C++17 |
|
2000 ms |
61860 KB |
#include <bits/stdc++.h>
#define fi(i, a, b) for( int i = a; i <= b; i++ )
#define fid(i, a, b) for( int i = a; i >= b; i-- )
#define getbit(x, i) ((x>>i)&1)
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define st first
#define nd second
#define mp make_pair
#define HTManh ""
#define maxn 100009
#define endl '\n'
using namespace std;
int n, m, s;
pll a[300009];
pll st[3][1200009];
void build(int goc = 1, int l = 1, int r = n)
{
if (l == r)
{
st[0][goc] = {a[l].st, l};
st[1][goc] = {a[l].nd, l};
st[2][goc] = {a[l].nd - a[l].st, l};
return;
}
int mid = (l+r)/2;
build(goc*2,l,mid);
build(goc*2+1,mid+1,r);
st[0][goc] = min(st[0][goc*2], st[0][goc*2+1]);
st[1][goc] = max(st[1][goc*2], st[1][goc*2+1]);
st[2][goc] = max(st[2][goc*2], st[2][goc*2+1]);
}
void update(int vt, int goc = 1, int l = 1, int r = n)
{
if (vt < l || vt > r) return;
if (l == r)
{
st[0][goc].st = 1e9;
st[1][goc].st = -1e9;
st[2][goc].st = -2e9;
return;
}
int mid = (l+r)/2;
update(vt,goc*2,l,mid);
update(vt,goc*2+1,mid+1,r);
st[0][goc] = min(st[0][goc*2], st[0][goc*2+1]);
st[1][goc] = max(st[1][goc*2], st[1][goc*2+1]);
st[2][goc] = max(st[2][goc*2], st[2][goc*2+1]);
}
pll get(int tt, int d, int c, int goc = 1, int l = 1, int r = n)
{
if (c < l || d > r)
{
if (tt == 0) return {1e9, 0}; else return {-2e9, 0};
}
if (d <= l && r <= c) return st[tt][goc];
int mid = (l+r)/2;
if (tt == 0) return min(get(tt,d,c,goc*2,l,mid), get(tt,d,c,goc*2+1,mid+1,r));
else return max(get(tt,d,c,goc*2,l,mid), get(tt,d,c,goc*2+1,mid+1,r));
}
int bit[100009];
void capnhat(int vt, int gt)
{
while(vt <= n)
{
bit[vt] += gt;
vt += (vt & -vt);
}
}
int lay(int vt)
{
int s = 0;
while (vt > 0)
{
s += bit[vt];
vt -= (vt & -vt);
}
return s;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
if (fopen(HTManh".inp", "r"))
{
freopen(HTManh".inp", "r", stdin);
freopen(HTManh".out", "w", stdout);
}
cin >> n >> m >> s;
fi(i,1,n) cin >> a[i].st >> a[i].nd;
sort(a+1,a+n+1,greater<pll>());
//fi(i,1,n) cout << a[i].st << " " << a[i].nd << endl;
build();
int sl = m + s;
ll res = 0;
fi(i,1,n)
{
if (i <= sl) res += a[i].st;
capnhat(i,1);
}
//cout << res << endl;
fi(i,1,s)
{
pll gt0 = get(0,1,sl);
pll gt1 = get(1,sl+1,n);
pll gt2 = get(2,1,sl);
//cout << gt0.st << " " << gt1.st << " " << gt2.st << endl;
int del;
if (gt1.st - gt0.st >= gt2.st)
{
del = gt1.nd;
res += gt1.st - gt0.st;
}
else
{
del = gt2.nd;
res += gt2.st;
}
//cout << del << " " << res << endl;
update(del);
if (del > sl)
{
int dau = 1, cuoi = n;
while(dau <= cuoi)
{
int giua = (dau+cuoi)/2;
if (lay(giua) < lay(sl) - 1) dau = giua + 1;
else cuoi = giua - 1;
}
sl = lay(dau);
}
capnhat(del, -1);
}
cout << res << endl;
}
Compilation message
school.cpp: In function 'int main()':
school.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
98 | freopen(HTManh".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
school.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | freopen(HTManh".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 8 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 9 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 11 |
Incorrect |
3 ms |
8540 KB |
Output isn't correct |
| 12 |
Incorrect |
3 ms |
8540 KB |
Output isn't correct |
| 13 |
Incorrect |
7 ms |
14936 KB |
Output isn't correct |
| 14 |
Incorrect |
24 ms |
23000 KB |
Output isn't correct |
| 15 |
Incorrect |
34 ms |
35408 KB |
Output isn't correct |
| 16 |
Execution timed out |
2062 ms |
35408 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2066 ms |
35924 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2060 ms |
36180 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2013 ms |
36432 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2066 ms |
61860 KB |
Time limit exceeded |
