Submission #97198

#	Time	Username	Problem	Language	Result	Execution time	Memory
97198		Kastanda	Schools (IZhO13_school)	C++11	100 / 100	263 ms	52708 KiB

school

#include<bits/stdc++.h>
#define lc (id << 1)
#define rc (id << 1 ^ 1)
#define md ((l + r) >> 1)
using namespace std;
typedef long long ll;
template < int MXN >
struct SegTree
{
    ll K = 0;
    ll C[MXN * 8];
    ll S[MXN * 8];
    SegTree ()
    {
        K = 0;
        memset(C, 0, sizeof(C));
        memset(S, 0, sizeof(S));
    }
    void Add(int i, int val, int id = 1, int l = 0, int r = MXN)
    {
        if (r - l < 2)
        {
            S[id] += 1LL * val * i;
            C[id] += val; return ;
        }
        if (i < md)
            Add(i, val, lc, l, md);
        else
            Add(i, val, rc, md, r);
        C[id] = C[lc] + C[rc];
        S[id] = S[lc] + S[rc];
    }
    ll _Get(int id = 1, int l = 0, int r = MXN)
    {
        if (K == 0)
            return (0LL);
        if (C[id] <= K)
        {
            K -= C[id];
            return (S[id]);
        }
        if (r - l < 2)
        {
            ll ret = K * l;
            K = 0;
            return (ret);
        }
        return (_Get(rc, md, r) + _Get(lc, l, md));
    }
    ll Get(int k)
    {
        K = k;
        ll ret = _Get();
        assert(K == 0);
        return (ret);
    }
};
const int N = 300005, MXN = 100005;
int n, R, M;
pair < int , int > A[N];
int32_t main()
{
    scanf("%d%d%d", &n, &R, &M);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &A[i].first, &A[i].second);
    sort(A, A + n); reverse(A, A + n);
    SegTree < MXN * 2 > P, S;
    for (int i = 0; i < n; i++)
        S.Add(A[i].second, 1);
    ll Mx = 0, sum = 0;
    for (int i = 0; i < R + M; i++)
    {
        sum += A[i].first;
        S.Add(A[i].second, -1);
        P.Add(A[i].second - A[i].first + MXN, 1);
        if (i >= R - 1)
            Mx = max(Mx, sum + P.Get(i + 1 - R) - 1LL * (i + 1 - R) * MXN + S.Get(M - (i + 1 - R)));
    }
    return !printf("%lld\n", Mx);
}

Compilation message (stderr)

school.cpp: In function 'int32_t main()':
school.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &R, &M);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
school.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &A[i].first, &A[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100