Submission #97195

#	Time	Username	Problem	Language	Result	Execution time	Memory
97195		Kastanda	Schools (IZhO13_school)	C++11	65 / 100	207 ms	42744 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
{
    int C[MXN * 4];
    ll S[MXN * 4];
    SegTree ()
    {
        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 &k, int id = 1, int l = 0, int r = MXN)
    {
        if (k <= 0) return (0LL);
        if (C[id] <= k)
            {k -= C[id]; return (S[id]);}
        return (_Get(k, rc, md, r) + _Get(k, lc, l, md));
    }
    ll Get(int k)
    {
        int tmp = k;
        ll ret = _Get(tmp);
        assert(tmp == 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:51: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:53: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: 65 / 100