oj.uz

Submission #97195

# Submission time Handle Problem Language Result Execution time Memory
97195 2019-02-14T10:03:07 Z Kastanda Schools (IZhO13_school) C++11
65 / 100
 207 ms 42744 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19072 KB Output is correct
2 Correct 17 ms 19200 KB Output is correct
3 Correct 17 ms 19072 KB Output is correct
4 Runtime error 39 ms 38136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 19 ms 19072 KB Output is correct
6 Correct 19 ms 19072 KB Output is correct
7 Correct 20 ms 19200 KB Output is correct
8 Correct 22 ms 19200 KB Output is correct
9 Correct 25 ms 19192 KB Output is correct
10 Correct 19 ms 19200 KB Output is correct
11 Correct 20 ms 19072 KB Output is correct
12 Correct 25 ms 19192 KB Output is correct
13 Correct 42 ms 19448 KB Output is correct
14 Correct 74 ms 19704 KB Output is correct
15 Incorrect 105 ms 20276 KB Output isn't correct
16 Incorrect 207 ms 20552 KB Output isn't correct
17 Runtime error 194 ms 41592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 160 ms 41848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 159 ms 42248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 184 ms 42744 KB Execution killed with signal 11 (could be triggered by violating memory limits)