Submission #944511

#	Time	Username	Problem	Language	Result	Execution time	Memory
944511		tset	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	1092 ms	71040 KiB

sterilizing

#include<bits/stdc++.h> 
using namespace std;

#define int long long

const int T = 131072;
const int NB_SEGTREE = 32;
const int INF = 1e18+42;

void upd(int nde, vector<int>& ab)
{
    ab[nde] = ab[nde*2] + ab[nde*2 +1];
    if(nde > 1)
        upd(nde/2, ab);
}

void setValue(int pos, int value, vector<int>& ab)
{
    ab[pos + T] = value;
    upd((pos + T)/2, ab);
}

int query(int nde, int RB, int RE, int GB, int GE, vector<int>& ab)
{
    if(RB > GE || RE < GB)
        return 0;
    if(RB >= GB && RE <= GE)
        return ab[nde];
    int mid = (RB + RE)/2;
    return query(nde*2, RB, mid, GB, GE, ab) + query(nde*2 +1, mid+1, RE, GB, GE, ab);
}
signed main()
{
    int ctr = 0;
    int N, Q, K;
    scanf("%lld%lld%lld", &N, &Q, &K);
    vector<vector<int > > ABs(NB_SEGTREE, vector<int>(2*T, 0));
    for(int iN = 0; iN < N; iN++)
    {
        int value;
        scanf("%lld", &value);
        setValue(iN, value, ABs[0]);
    }
    set<pair<int, int>> debInterSet; // posi, prof;
    debInterSet.insert({0, 0});
    debInterSet.insert({N, -1});
    for(int iQ = 0; iQ < Q; iQ++)
    {
        int type, Ti, Ui;
        scanf("%lld%lld%lld", &type, &Ti, &Ui);
        //printf("%lld %lld %lld\n", type, Ti, Ui);

        if(type == 1)
        {
            int id = Ti, newValue = Ui;
            id--;
            auto it = debInterSet.upper_bound(pair<int, int>(id, +INF));
            int finInterEx = (*(it)).first;
            it--;
            int debInter = (*(it)).first;
            int profInter = (*(it)).second;
            int newProf = 0;
            if(id+1 <finInterEx)
                debInterSet.insert({id+1, profInter});
            if(debInter == id)
                debInterSet.erase(it);
            debInterSet.insert({id, newProf});
            setValue(id, 0, ABs[profInter]);
            setValue(id, newValue, ABs[0]);
        }
        else if(type == 2)
        {
            if(K!=1)
            {
                int l = Ti, r = Ui;
                l--; r--;
                while (l <= r)
                {
                    auto itAfter = debInterSet.upper_bound(pair<int, int>(l, +INF));
                    auto itBefore = debInterSet.upper_bound(pair<int, int>(l, +INF)); 
                    itBefore--;                   
                    int finInterEx = (*(itAfter)).first;
                    int profNextCheck = (*(itAfter)).second;
                    int debInter = (*(itBefore)).first;
                    int profInter = (*(itBefore)).second;
                    while (profNextCheck == profInter)
                    {
                        auto itsuppr = debInterSet.upper_bound(pair<int, int>(l, +INF));
                        debInterSet.erase(itsuppr);
                        itAfter = debInterSet.upper_bound(pair<int, int>(l, +INF));
                        finInterEx = (*(itAfter)).first;
                        profNextCheck = (*(itAfter)).second;
                    }
                    int newProf = profInter+1;
                    if(profInter == NB_SEGTREE-1)
                    {
                        l = min(finInterEx, r+1);
                        continue;
                    }
                    if(r+1 <finInterEx)
                        debInterSet.insert({r+1, profInter});
                    if(debInter == l)
                        debInterSet.erase(itBefore);
                    debInterSet.insert({l, newProf});

                    for(int pt = l; pt <min(finInterEx, r+1); pt++)
                    {
                        ctr ++;

                        int valuePt = ABs[profInter][pt+T];
                        setValue(pt, 0, ABs[profInter]);
                        setValue(pt, valuePt/K, ABs[newProf]);
                    }
                    l = min(finInterEx, r+1);
                }
            }
        }
        else if(type == 3)
        {
            int l = Ti, r = Ui;
            l--; r--;
            int res = 0;
            for(int iAB = 0; iAB < NB_SEGTREE; iAB++)
            {
                res += query(1, 0, T-1, l, r, ABs[iAB]);
            }
            printf("%lld\n", res);
        }
        /*printf("%lld\n", ctr);
        for(auto v : debInterSet)
        {
            printf("%lld/%lld - ", v.first, v.second);
        }
        printf("\n");*/
    }


}

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%lld%lld%lld", &N, &Q, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%lld", &value);
      |         ~~~~~^~~~~~~~~~~~~~~~
sterilizing.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         scanf("%lld%lld%lld", &type, &Ti, &Ui);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75