oj.uz

Submission #944504

# Submission time Handle Problem Language Result Execution time Memory
944504 2024-03-12T20:13:18 Z tset Sterilizing Spray (JOI15_sterilizing) C++17
15 / 100
 5000 ms 72084 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 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, 0});
    for(int iQ = 0; iQ < Q; iQ++)
    {
        int type, Ti, Ui;
        scanf("%lld%lld%lld", &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 it = debInterSet.upper_bound(pair<int, int>(l, +INF));                    
                    int finInterEx = (*(it)).first;
                    it--;
                    int debInter = (*(it)).first;
                    int profInter = (*(it)).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(it);
                    debInterSet.insert({l, newProf});

                    for(int pt = l; pt <min(finInterEx, r+1); pt++)
                    {
                        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);
        }

    }


}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%lld%lld%lld", &N, &Q, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         scanf("%lld", &value);
      |         ~~~~~^~~~~~~~~~~~~~~~
sterilizing.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         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 26 ms 68124 KB Output is correct
3 Correct 28 ms 68180 KB Output is correct
4 Correct 53 ms 68280 KB Output is correct
5 Correct 50 ms 68188 KB Output is correct
6 Correct 50 ms 68440 KB Output is correct
7 Correct 50 ms 68184 KB Output is correct
8 Correct 51 ms 68184 KB Output is correct
9 Correct 53 ms 68172 KB Output is correct
10 Correct 51 ms 68188 KB Output is correct
11 Correct 50 ms 68132 KB Output is correct
12 Correct 51 ms 68176 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 70272 KB Output is correct
2 Correct 318 ms 70108 KB Output is correct
3 Correct 298 ms 70108 KB Output is correct
4 Correct 401 ms 71244 KB Output is correct
5 Correct 477 ms 72012 KB Output is correct
6 Correct 497 ms 72008 KB Output is correct
7 Correct 481 ms 72012 KB Output is correct
8 Correct 484 ms 72084 KB Output is correct
9 Correct 281 ms 71868 KB Output is correct
10 Correct 236 ms 71972 KB Output is correct
11 Correct 240 ms 72016 KB Output is correct
12 Correct 240 ms 72064 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1164 ms 68176 KB Output is correct
2 Correct 549 ms 68184 KB Output is correct
3 Correct 1180 ms 68180 KB Output is correct
4 Execution timed out 5037 ms 68540 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5012 ms 69656 KB Time limit exceeded
2 Halted 0 ms 0 KB -