oj.uz

Submission #944476

# Submission time Handle Problem Language Result Execution time Memory
944476 2024-03-12T18:27:42 Z tset Sterilizing Spray (JOI15_sterilizing) C++14
5 / 100
 5000 ms 68188 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 = upper_bound(debInterSet.begin(), debInterSet.end(), 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 = upper_bound(debInterSet.begin(), debInterSet.end(), 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++)
                    {
                        //printf("%lld %lld-%lld\n", pt, profInter, newProf);
                        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 51 ms 68160 KB Output is correct
2 Correct 29 ms 68188 KB Output is correct
3 Correct 34 ms 68180 KB Output is correct
4 Correct 1336 ms 68188 KB Output is correct
5 Correct 2562 ms 68188 KB Output is correct
6 Correct 2791 ms 68184 KB Output is correct
7 Correct 2869 ms 68188 KB Output is correct
8 Correct 2612 ms 68180 KB Output is correct
9 Correct 2827 ms 68184 KB Output is correct
10 Correct 2623 ms 68180 KB Output is correct
11 Correct 2847 ms 68180 KB Output is correct
12 Correct 2867 ms 68188 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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