Submission #1135934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135934		MateiKing80	Watering can (POI13_kon)	C++20	80 / 100	1795 ms	117196 KiB

kon

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll
const int NMAX = 300000, B = 700, LBOZO = 100000;
ll N, K, t[NMAX + 5], zeros[NMAX + 5], ans[NMAX + 5];
signed mp[332][LBOZO + 5];

void inicjuj(signed n, signed k, signed *D)
{
    for(int i = 0; i < n; i ++)
        t[i] = D[i];
    N = n, K = k;
    for(int i = 0; i < n; i ++)
    {
        if(K >= t[i] && K - t[i] <= LBOZO)
            mp[i / B][-(K - t[i]) + LBOZO] ++;
        if(t[i] >= K)
            ans[i / B] ++;
    }
}

void podlej(signed a, signed b)
{
    int from = a/B, to = (b / B);
    for(int i = from; i <= to; i ++)
    {
        if(a <= i * B && b >= (i + 1) * B - 1)
        {
            zeros[i]++;
            ans[i] += mp[i][LBOZO - zeros[i]];
        }
        else
        {
            ans[i] = 0;
            for(int j = i * B; j / B == i && j < N; j ++)
            {
                if(K >= t[j] && K - t[j] <= LBOZO)
                    mp[i][-(K - t[j]) + LBOZO] --;
                t[j] += zeros[i];
                if(j >= a && j <= b)
                    t[j] ++;
                if(K >= t[j] && K - t[j] <= LBOZO)
                    mp[i][- (K - t[j]) + LBOZO] ++;
                if(t[j] >= K)
                    ans[i]++;
            }
            zeros[i] = 0;
        }
    }
}

signed dojrzale(signed a, signed b)
{
    int rasp = 0;
    int from = a / B, to = (b / B);
    for(int i = from; i <= to; i ++)
    {
        if(a <= i * B && b >= (i + 1) * B - 1)
            rasp += ans[i];
        else
        {
            for(int j = max(1ll * a, i * B); j / B == i && j <= b; j ++)
                rasp += (t[j] + zeros[i] >= K);
        }
    }
    return rasp;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10