Submission #1043907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043907		vjudge1	Schools (IZhO13_school)	C++17	70 / 100	2074 ms	61644 KiB

school

#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 << sl << "|" << 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 = dau;
        }
        capnhat(del, -1);
    }
    cout << res << endl;
}

Compilation message (stderr)

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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 70 / 100