Submission #1134190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134190		alexdd	Watering can (POI13_kon)	C++20	0 / 100	4094 ms	6692 KiB

kon

#include<bits/stdc++.h>
using namespace std;
const int BUC = 500;
int a[300005];
int aib[300005],cate;
vector<pair<int,int>> v[10005];
int scade[10005];
int qry(int poz)
{
    poz++;
    int aux=0;
    for(int i=poz;i>0;i-=(i&(-i)))
        aux+=aib[i];
    return aux;
}
void upd(int poz, int newv)
{
    poz++;
    for(int i=poz;i<=cate;i+=(i&(-i)))
        aib[i]+=newv;
}

void inicjuj(int n, int k, int *D)
{
    cate=n;
    for(int i=0;i<=n;i++)
        aib[i]=0;
    for(int i=0;i<n;i++)
    {
        a[i] = max(0, k - D[i]);
    }
    for(int i=0;i<n;i+=BUC)
    {
        for(int j=i;j<min(n,i+BUC);j++)
            if(a[j]>0)
                v[i/BUC].push_back({a[j],j});
        sort(v[i/BUC].begin(),v[i/BUC].end());
    }
}
void podlej(int le, int ri)
{
    vector<pair<int,int>> newv;
    for(auto x:v[le/BUC])
    {
        if(le <= x.second && ri <= x.second)
        {
            if(x.first-1 == 0)
                upd(x.second, +1);
            else
                newv.push_back({x.first-1,x.second});
        }
        else
            newv.push_back(x);
    }
    v[le/BUC] = newv;
    if(le/BUC != ri/BUC)
    {
        newv.clear();
        for(auto x:v[ri/BUC])
        {
            if(le <= x.second && ri <= x.second)
            {
                if(x.first-1 == 0)
                    upd(x.second, +1);
                else
                    newv.push_back({x.first-1,x.second});
            }
            else
                newv.push_back(x);
        }
        v[ri/BUC] = newv;
    }
    for(int b=le/BUC+1;b<ri/BUC;b++)
    {
        newv.clear();
        for(auto x:v[b])
        {
            if(le <= x.second && ri <= x.second)
            {
                if(x.first-1 == 0)
                    upd(x.second, +1);
                else
                    newv.push_back({x.first-1,x.second});
            }
            else
                newv.push_back(x);
        }
        v[b] = newv;
    }
}
int dojrzale(int le, int ri)
{
    return qry(ri)-qry(le-1);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 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