oj.uz

Submission #852711

# Submission time Handle Problem Language Result Execution time Memory
852711 2023-09-22T14:44:15 Z tvgk Holiday (IOI14_holiday) C++17
30 / 100
 45 ms 9060 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define task ""
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 1e5 + 7;
 
ii tree[mxN * 4], a[mxN];
ll num, mx, tmp, ans, vt[mxN];
int j;
 
void Up(int j)
{
    tree[j].se = tree[j * 2].se + tree[j * 2 + 1].se;
 
    tree[j].fi = 0;
    if (tree[j * 2].se)
        tree[j].fi += tree[j * 2].fi;
    if (tree[j * 2 + 1].se)
        tree[j].fi += tree[j * 2 + 1].fi;
}
 
void Build(int j, int l, int r)
{
    if (l == r)
    {
        tree[j].fi = a[l].fi;
        return;
    }
 
    int mid = (l + r) / 2;
    Build(j * 2, l, mid);
    Build(j * 2 + 1, mid + 1, r);
}
 
ll Get(int j, int l, int r)
{
  	if ((!tree[j].se) || (num <= 0))
        return 0;
  
    if (tree[j].se <= num)
    {
        num -= tree[j].se;
        return tree[j].fi;
    }
 
    int mid = (l + r) / 2;
    return Get(j * 2 + 1, mid + 1, r) + Get(j * 2, l, mid);
}
 
void Update(int j, int l, int r, int vt, int tt)
{
    if (l > vt || vt > r)
        return;
 
    if (l == r)
    {
        tree[j].se = tt;
        return;
    }
 
    int mid = (l + r) / 2;
    Update(j * 2, l, mid, vt, tt);
    Update(j * 2 + 1, mid + 1, r, vt, tt);
 
    Up(j);
}
 
long long int findMaxAttraction(int n, int stt, int day, int att[])
{
    stt++;
    for (int i = 1; i <= n; i++)
    {
        a[i].fi = att[i - 1];
        a[i].se = i;
    }
 
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
        vt[a[i].se] = i;
 
    Build(1, 1, n);
    for (int i = stt; i <= n; i++)
    {
      	Update(1, 1, n, vt[i], 1);

     	num = day - (i - stt);
        mx = Get(1, 1, n);
      	ans = max(ans, mx);
    }
 
    j = n;
    for (int i = stt; i >= 1; i--)
    {
        Update(1, 1, n, vt[i], 1);
        num = day - (j - i) - min(stt - i, j - stt);
        mx = Get(1, 1, n);
 
        while (j > stt)
        {
            Update(1, 1, n, vt[j], 0);
            j--;
 
            num = day - (j - i) - min(stt - i, j - stt);
            tmp = Get(1, 1, n);
 
            if (tmp >= mx)
                mx = tmp;
            else
            {
                j++;
                Update(1, 1, n, vt[j], 1);
                break;
            }
        }
 
        ans = max(ans, mx);
    }
 
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4696 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 9052 KB Output is correct
2 Correct 34 ms 9028 KB Output is correct
3 Correct 23 ms 9052 KB Output is correct
4 Correct 45 ms 9060 KB Output is correct
5 Correct 37 ms 9052 KB Output is correct
6 Correct 11 ms 5024 KB Output is correct
7 Correct 18 ms 7260 KB Output is correct
8 Correct 25 ms 7148 KB Output is correct
9 Correct 7 ms 4956 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5208 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Incorrect 2 ms 4956 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 9052 KB Output is correct
2 Correct 25 ms 9052 KB Output is correct
3 Incorrect 22 ms 7004 KB Output isn't correct
4 Halted 0 ms 0 KB -