답안 #39861 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
39861	2018-01-22T08:45:19 Z	grumpy_gordon	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	216 ms	8744 KB

sterilizing

/*
                     .:*+=%@@@@@@=-.
                 .:=@#@@@#@@#######%==*.
              .-=####@######%*-.....:%##%.
            .*@###########%+:--........-%@-
          .*@##############@+--.........-:%-
        .+##################@==%%%%=+*:----+.
      .-@####################%++%@@@@@=+**%@@*
      .%###################@%%@@@###@%+:--%@@%.
     -@###################@%%%%*::*%++:-----=@+.
    -#####################@%=++++++*:-------.-=:
   .+####################@%++*::-:::--::*:::***=:
   .@#####################%=++*::::-:::++*=##@@#@-
  ..#####################@%%=++**:::::**+%@#@%%##-..
   .%####################@@%=+++*+****::*=@######@.
  .=######################@%%==+==++**+=@%@##@###+:...
  -#######################@@@%%%===++=@@@%=++===*::--...
  -########################@@@@@@@%==%%=++==@@:::::*:--.
..:#########################@@@@@@%%======++++::-..:-.--...
%#############################@###@%%@@%==%=%*----.--.::---.
#############################################*-:*:-:---*---- .
#############################################*--*--:---*---:-.
#############################################+--::--::-*::-::.
###########################################+:*-.---.---.:---*-..
###########################################**:-----------------.
##########################################@::**:--::::::--:::::-
###########################################:--:*:::::::::**::*+*
###########################################=:::***::::::**:::*+*
############################@@@@@@#########@+****::::********+++
############################@%%%%%@@@@@@@###%+***::::::::***+==+
############################@%%%%%%%%%%%@####=+:::-::::-::*+=%%+
#############################@%%%%%%%%%%@#####=::--------:*=%@%+
%###########################@%%%%==%%%%%%@##@#=:------..-:+%@@%=
----------------------------------------------
--------------------------------------------
----------------------------------------------
--------------------------------------------
----------------------------------------------

         o###########oo
      o##"          ""##o
    o#"                "##
  o#"                    "#o
 #"  ##              ##   "##
#"                          ##
#  ###################       #
#                            #
#                            #
#                            #
#                            #
#                            #
#                            #
#o                           #
"#o                         ##
 "#o                       ##
  "#o                    o#"
   "#o                  ##
     "#o              o#"
       "#ooo      ooo#######oo
        ###############   "######o
     o###""        "###o      # ###
   o###o     oooo    ###    oo####"
 o###**#     #**#   ############"
 ""##""""""""""###########    #
    # oooooooo#"#**     ##    #
    # #       # # **    ##    #
    #o#       #o#  *****###ooo#
                        ##
                        ##   o###o
                        ## o##***##
               o########## #***#**##o
             o##"   ""###  #***##***#
 o#######o  ###   oo####   ##**####*#
o##"  ""#############""     ##****###
##"         ##              ##*##*###
##          ###              ##### ##
##           ###              # ##  #
##            ##                 #
##             ##
##             ###
##              ###oo
###              ""###
 ###
  ###
*/
#include <bits/stdc++.h>

//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
//float __attribute__((aligned(32)))

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

int mysqrt(ll x){
    int l = 0, r = 1e9 + 1;
    while (r - l > 1){
        int m = (l + r) / 2;
        if (m * (ll)m <= x)
            l = m;
        else
            r = m;
    }
    return l;
}

mt19937 rnd(1337);

ll AR = 19, BR = 13, CR = 23, XR = 228, YR = 322, MODR = 1e9 + 993;

ll myrand(){
    ll ZR = (XR * AR + YR * BR + CR) % MODR;
    XR = YR;
    YR = ZR;
    return ZR;
}

const int Mod = 1e9 + 7;

int bpow(int x, int y){
    if (y == 0)
        return 1;
    if (y == 1)
        return x;
    int ret = bpow(x, y >> 1);
    ret = (ret * (ll)ret) % Mod;
    if (y & 1)
        ret = (ret * (ll)x) % Mod;
    return ret;
}

int bdiv(int x, int y){
    return (x * (ll)bpow(y, Mod - 2)) % Mod;
}

void setmin(int &x, int y){
    x = min(x, y);
}

void setmax(int &x, int y){
    x = max(x, y);
}

int gcd(int a, int b){
    return a ? gcd(b % a, a) : b;
}

const ll llinf = 2e18 + 100;

const int maxn = 1e5 + 100, maxw = (1 << 17) + 100, inf = 2e9 + 100, sq = 300, mod = 1e9 + 7, LG = 17;

int n, k, zap;

int a[maxn];

set<int> q;

ll fen[maxn];

void inc(int i, int v){
    for (; i < n; i = (i | (i + 1)))
        fen[i] += v;
}

ll get(int i){
    ll v = 0;
    for (; i >= 0; i = (i & (i + 1)) - 1)
        v += fen[i];
    return v;
}

int main()
{
    #ifdef ONPC
    //ifstream cin("a.in");
    //ofstream cout("a.out");
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    #else
    //ifstream cin("sprinklers.in");
    //ofstream cout("sprinklers.out");
    //freopen("road.in", "r", stdin);
    //freopen("road.out", "w", stdout);
    #endif // ONPC
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    //cout.tie(0);
    //cin >> n >> zap >> k;
    scanf("%d%d%d", &n, &zap, &k);
    for (int i = 0; i < n; i++){
        //cin >> a[i];
        scanf("%d", &a[i]);
        inc(i, a[i]);
        if (a[i])
            q.insert(i);
    }
    while (zap--){
        int t, A, B;
        scanf("%d%d%d", &t, &A, &B);
        //cin >> t >> A >> B;
        A--;
        if (t == 1){
            if (!B && a[A])
                q.erase(A);
            if (B && !a[A])
                q.insert(A);
            inc(A, B - a[A]);
            a[A] = B;
            continue;
        }
        B--;
        if (t == 3)
            printf("%lld\n", get(B) - get(A - 1));
        else{
            if (k == 1)
                continue;
            vector<int> p;
            set<int> :: iterator it = q.lower_bound(A);
            while (it != q.end() && *it <= B){
                inc(*it, a[*it] / k - a[*it]);
                a[*it] /= k;
                if (!a[*it])
                    p.push_back(*it);
                it++;
            }
            for (auto i : p)
                q.erase(i);
        }
    }
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:196:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &zap, &k);
                                  ^
sterilizing.cpp:199:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
                           ^
sterilizing.cpp:206:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &t, &A, &B);
                                    ^

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	3200 KB	Output is correct
2	Correct	1 ms	3200 KB	Output is correct
3	Correct	0 ms	3332 KB	Output is correct
4	Correct	4 ms	3332 KB	Output is correct
5	Correct	5 ms	3332 KB	Output is correct
6	Correct	7 ms	3332 KB	Output is correct
7	Correct	6 ms	3332 KB	Output is correct
8	Correct	2 ms	3332 KB	Output is correct
9	Correct	5 ms	3332 KB	Output is correct
10	Correct	2 ms	3332 KB	Output is correct
11	Correct	5 ms	3332 KB	Output is correct
12	Correct	5 ms	3332 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	60 ms	5444 KB	Output is correct
2	Correct	73 ms	4784 KB	Output is correct
3	Correct	57 ms	6896 KB	Output is correct
4	Correct	103 ms	7820 KB	Output is correct
5	Correct	84 ms	7952 KB	Output is correct
6	Correct	92 ms	7952 KB	Output is correct
7	Correct	103 ms	7952 KB	Output is correct
8	Correct	97 ms	7952 KB	Output is correct
9	Correct	92 ms	7952 KB	Output is correct
10	Correct	92 ms	7952 KB	Output is correct
11	Correct	93 ms	7952 KB	Output is correct
12	Correct	92 ms	7952 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	3332 KB	Output is correct
2	Correct	22 ms	4256 KB	Output is correct
3	Correct	22 ms	4396 KB	Output is correct
4	Correct	49 ms	3868 KB	Output is correct
5	Correct	82 ms	5744 KB	Output is correct
6	Correct	90 ms	5576 KB	Output is correct
7	Correct	79 ms	5576 KB	Output is correct
8	Correct	76 ms	5576 KB	Output is correct
9	Correct	76 ms	6004 KB	Output is correct
10	Correct	67 ms	6004 KB	Output is correct
11	Correct	72 ms	6000 KB	Output is correct
12	Correct	69 ms	6000 KB	Output is correct

Subtask #4
75.0 / 75.0

#	결과	실행 시간	메모리	Grader output
1	Correct	84 ms	5716 KB	Output is correct
2	Correct	99 ms	5708 KB	Output is correct
3	Correct	98 ms	5312 KB	Output is correct
4	Correct	104 ms	4784 KB	Output is correct
5	Correct	161 ms	8096 KB	Output is correct
6	Correct	159 ms	7952 KB	Output is correct
7	Correct	151 ms	7952 KB	Output is correct
8	Correct	196 ms	7952 KB	Output is correct
9	Correct	169 ms	8744 KB	Output is correct
10	Correct	194 ms	8484 KB	Output is correct
11	Correct	154 ms	8744 KB	Output is correct
12	Correct	216 ms	8484 KB	Output is correct

답안 #39861

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 10.0 / 10.0

Subtask #4 75.0 / 75.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
10.0 / 10.0

Subtask #4
75.0 / 75.0