oj.uz

답안 #944447

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
944447 2024-03-12T17:53:14 Z tset Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 226 ms 267796 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)
        {
            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(r+1 <finInterEx)
                    debInterSet.insert({r+1, profInter});
                if(debInter == l)
                    debInterSet.erase(it);
                debInterSet.insert({l, newProf});


                finInterEx = min(finInterEx, r+1);
                if(profInter == NB_SEGTREE-1)
                {
                    l = finInterEx;
                    continue;
                }
                for(int pt = l; pt <finInterEx; pt++)
                {
                    int valuePt = ABs[profInter][pt+T];
                    setValue(pt, 0, ABs[profInter]);
                    setValue(pt, valuePt/K, ABs[newProf]);
                }
                l = finInterEx;
            }
        }
        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:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%lld%lld%lld", &N, &Q, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         scanf("%lld", &value);
      |         ~~~~~^~~~~~~~~~~~~~~~
sterilizing.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         scanf("%lld%lld%lld", &type, &Ti, &Ui);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 162 ms 267084 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 226 ms 267672 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 167 ms 267084 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 201 ms 267796 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -