oj.uz

Submission #97193

# Submission time Handle Problem Language Result Execution time Memory
97193 2019-02-14T09:56:34 Z Kastanda Schools (IZhO13_school) C++11
65 / 100
 253 ms 10552 KB 
#include<bits/stdc++.h>
#define lc (id << 1)
#define rc (id << 1 ^ 1)
#define md ((l + r) >> 1)
#define int long long
using namespace std;
typedef long long ll;
template < int MXN >
struct SegTree
{
    int C[MXN * 4];
    ll S[MXN * 4];
    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 = 400005, MXN = 200005;
int n, R, M;
pair < int , int > A[N];
int32_t main()
{
    scanf("%lld%lld%lld", &n, &R, &M);
    for (int i = 0; i < n; i++)
        scanf("%lld%lld", &A[i].first, &A[i].second);
    sort(A, A + n); reverse(A, A + n);
    SegTree < MXN * 4 > 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:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld%lld", &n, &R, &M);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
school.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld", &A[i].first, &A[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
65.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Runtime error 9 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 4 ms 2176 KB Output is correct
6 Correct 5 ms 3328 KB Output is correct
7 Correct 10 ms 3840 KB Output is correct
8 Correct 10 ms 4736 KB Output is correct
9 Correct 13 ms 4480 KB Output is correct
10 Correct 11 ms 4480 KB Output is correct
11 Correct 10 ms 4480 KB Output is correct
12 Correct 10 ms 4352 KB Output is correct
13 Correct 41 ms 5084 KB Output is correct
14 Correct 79 ms 5036 KB Output is correct
15 Incorrect 108 ms 6008 KB Output isn't correct
16 Incorrect 253 ms 7504 KB Output isn't correct
17 Runtime error 121 ms 8056 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 138 ms 8808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 184 ms 9500 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 193 ms 10552 KB Execution killed with signal 11 (could be triggered by violating memory limits)