oj.uz

Submission #944511

# Submission time Handle Problem Language Result Execution time Memory
944511 2024-03-12T20:48:58 Z tset Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 1092 ms 71040 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 68188 KB Output is correct
2 Correct 25 ms 68176 KB Output is correct
3 Correct 28 ms 68188 KB Output is correct
4 Correct 38 ms 68184 KB Output is correct
5 Correct 45 ms 68132 KB Output is correct
6 Correct 45 ms 68188 KB Output is correct
7 Correct 50 ms 68184 KB Output is correct
8 Correct 51 ms 68176 KB Output is correct
9 Correct 42 ms 68176 KB Output is correct
10 Correct 42 ms 68212 KB Output is correct
11 Correct 45 ms 68180 KB Output is correct
12 Correct 42 ms 68188 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 68680 KB Output is correct
2 Correct 301 ms 68344 KB Output is correct
3 Correct 282 ms 68292 KB Output is correct
4 Correct 376 ms 69140 KB Output is correct
5 Correct 484 ms 69584 KB Output is correct
6 Correct 512 ms 69612 KB Output is correct
7 Correct 515 ms 69960 KB Output is correct
8 Correct 494 ms 69940 KB Output is correct
9 Correct 244 ms 69872 KB Output is correct
10 Correct 230 ms 69708 KB Output is correct
11 Correct 235 ms 69708 KB Output is correct
12 Correct 234 ms 69684 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 68392 KB Output is correct
2 Correct 228 ms 68188 KB Output is correct
3 Correct 284 ms 68184 KB Output is correct
4 Correct 644 ms 68184 KB Output is correct
5 Correct 1086 ms 68176 KB Output is correct
6 Correct 1092 ms 68188 KB Output is correct
7 Correct 486 ms 71040 KB Output is correct
8 Correct 1079 ms 68180 KB Output is correct
9 Correct 817 ms 68188 KB Output is correct
10 Correct 767 ms 68184 KB Output is correct
11 Correct 747 ms 68176 KB Output is correct
12 Correct 767 ms 68184 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 668 ms 68184 KB Output is correct
2 Correct 711 ms 68328 KB Output is correct
3 Correct 443 ms 68184 KB Output is correct
4 Correct 759 ms 68188 KB Output is correct
5 Correct 1079 ms 68924 KB Output is correct
6 Correct 1092 ms 68968 KB Output is correct
7 Correct 1083 ms 68868 KB Output is correct
8 Correct 1084 ms 68784 KB Output is correct
9 Correct 757 ms 68800 KB Output is correct
10 Correct 818 ms 68640 KB Output is correct
11 Correct 758 ms 68964 KB Output is correct
12 Correct 794 ms 68780 KB Output is correct