Submission #799122

#	Time	Username	Problem	Language	Result	Execution time	Memory
799122		bane	Watering can (POI13_kon)	C++17	20 / 100	1048 ms	131072 KiB

kon

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <string.h>
#include <bitset>
#include <numeric>
#include <utility>
#include<math.h>
using namespace std;
#define ll long long
const int nax = 300'001;
int sq = 500;
ll N, K, t[nax], zers[nax], ans[nax];

unordered_map<int,int>mapa[551];

void inicjuj(int n, int k, int *D)
{
    sq = min(500, (int)sqrt(n) + 1);
    for (int i = 0; i < n; i++){
        t[i] = D[i];
    }
    N = n, K = k;
    for (int i = 0; i < n; i++){
        mapa[i / sq][t[i]]++;
        if (t[i] >= K)ans[i / sq]++;
    }
    
}

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

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

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