oj.uz

Submission #944474

# Submission time Handle Problem Language Result Execution time Memory
944474 2024-03-12T18:20:08 Z tset Sterilizing Spray (JOI15_sterilizing) C++14
5 / 100
 5000 ms 136024 KB 
#include<bits/stdc++.h> 
using namespace std;

#define int long long

const int T = 262144;
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 73 ms 136016 KB Output is correct
2 Correct 38 ms 135896 KB Output is correct
3 Correct 43 ms 135756 KB Output is correct
4 Correct 1350 ms 135772 KB Output is correct
5 Correct 2565 ms 135764 KB Output is correct
6 Correct 2810 ms 135764 KB Output is correct
7 Correct 2630 ms 136016 KB Output is correct
8 Correct 2615 ms 135764 KB Output is correct
9 Correct 2826 ms 135840 KB Output is correct
10 Correct 2655 ms 135760 KB Output is correct
11 Correct 2863 ms 135760 KB Output is correct
12 Correct 2867 ms 136024 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5087 ms 135760 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 5040 ms 135772 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 135872 KB Time limit exceeded
2 Halted 0 ms 0 KB -