제출 #95008

#제출 시각아이디문제언어결과실행 시간메모리
95008bogdan10bosSterilizing Spray (JOI15_sterilizing)C++14
100 / 100
557 ms11384 KiB
#include <bits/stdc++.h> using namespace std; //#define FILE_IO typedef long long LL; const int NMAX = 1e5; int N, Q, K; vector<int> init; class SegmentTree { public: LL ans; vector<int> mx, mn, lzy; vector<LL> sum; void remake(int nod) { sum[nod] = sum[nod * 2] + sum[nod * 2 + 1]; mx[nod] = max(mx[nod * 2], mx[nod * 2 + 1]); mn[nod] = min(mn[nod * 2], mn[nod * 2 + 1]); } void lazy(int nod, int st, int dr) { if(lzy[nod] == -1) return; int mij = st + (dr - st) / 2; int val = lzy[nod]; lzy[nod * 2] = lzy[nod * 2 + 1] = val; sum[nod * 2] = 1LL * (mij - st + 1) * val; mx[nod * 2] = mn[nod * 2] = val; sum[nod * 2 + 1] = 1LL * (dr - mij) * val; mx[nod * 2 + 1] = mn[nod * 2 + 1] = val; lzy[nod] = -1; } void B(int nod, int st, int dr) { lzy[nod] = -1; if(st == dr) { sum[nod] = mn[nod] = mx[nod] = init[st]; return; } int mij = st + (dr - st) / 2; B(nod * 2, st, mij); B(nod * 2 + 1, mij + 1, dr); remake(nod); } void U(int nod, int st, int dr, int pos, int val) { if(st == dr) { sum[nod] = mx[nod] = mn[nod] = val; return; } lazy(nod, st, dr); int mij = st + (dr - st) / 2; if(pos <= mij) U(nod * 2, st, mij, pos, val); else U(nod * 2 + 1, mij + 1, dr, pos, val); remake(nod); } void U(int nod, int st, int dr, int sti, int dri, int val) { if(sti <= st && dr <= dri) { if(mn[nod] / val == mx[nod] / val) { mn[nod] = mx[nod] = mn[nod] / val; sum[nod] = 1LL * (dr - st + 1) * mn[nod]; lzy[nod] = mn[nod]; return; } lazy(nod, st, dr); int mij = st + (dr - st) / 2; U(nod * 2, st, mij, sti, dri, val); U(nod * 2 + 1, mij + 1, dr, sti, dri, val); remake(nod); return; } lazy(nod, st, dr); int mij = st + (dr - st) / 2; if(sti <= mij) U(nod * 2, st, mij, sti, dri, val); if(mij < dri) U(nod * 2 + 1, mij + 1, dr, sti, dri, val); remake(nod); } void Q(int nod, int st, int dr, int sti, int dri) { if(sti <= st && dr <= dri) { ans += sum[nod]; return; } lazy(nod, st, dr); int mij = st + (dr - st) / 2; if(sti <= mij) Q(nod * 2, st, mij, sti, dri); if(mij < dri) Q(nod * 2 + 1, mij + 1, dr, sti, dri); } void build() { sum.resize(4 * N + 2); mx.resize(4 * N + 2); mn.resize(4 * N + 2); lzy.resize(4 * N + 2); B(1, 1, N); } void update(int pos, int val) { U(1, 1, N, pos, val); } void divide(int st, int dr, int K) { if(K == 1) return; U(1, 1, N, st, dr, K); } LL query(int st, int dr) { ans = 0; Q(1, 1, N, st, dr); return ans; } }aint; void gen() { freopen("1.in", "w", stdout); mt19937 g(chrono::high_resolution_clock::now().time_since_epoch().count()); int N = 10, Q = 150; int VMAX = 100; int K = uniform_int_distribution<int>(2, 10)(g); printf("%d %d %d\n", N, Q, K); for(int i = 1; i <= N; i++) printf("%d ", uniform_int_distribution<int>(0, VMAX)(g)); printf("\n"); auto uid = uniform_int_distribution<int>(1, N); for(int i = 1; i <= Q; i++) { int op = g() % 3 + 1; if(op == 1) { int pos = uid(g); printf("%d %d %d\n", op, pos, uniform_int_distribution<int>(0, VMAX)(g)); } else { int st = uid(g), dr = uid(g); if(st > dr) swap(st, dr); printf("%d %d %d\n", op, st, dr); } } exit(0); } int main() { //gen(); #ifdef FILE_IO freopen("1.in", "r", stdin); //freopen("1.out", "w", stdout); #endif scanf("%d%d%d", &N, &Q, &K); init.resize(N + 2); for(int i = 1; i <= N; i++) scanf("%d", &init[i]); aint.build(); for(int q = 1; q <= Q; q++) { int op; scanf("%d", &op); if(op == 1) { int pos, val; scanf("%d%d", &pos, &val); aint.update(pos, val); // init[pos] = val; } else if(op == 2) { int st, dr; scanf("%d%d", &st, &dr); aint.divide(st, dr, K); // for(int i = st; i <= dr; i++) init[i] /= K; } else if(op == 3) { int st, dr; scanf("%d%d", &st, &dr); LL ans = aint.query(st, dr); printf("%lld\n", ans); // for(int i = st; i <= dr; i++) ans -= init[i]; // if(ans != 0) // { // cerr << "Assertion failed!" << '\n'; // ans++; // ans--; // } } } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

sterilizing.cpp: In function 'void gen()':
sterilizing.cpp:155:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("1.in", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:193:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &Q, &K);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:195:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= N; i++) scanf("%d", &init[i]);
                                 ~~~~~^~~~~~~~~~~~~~~~
sterilizing.cpp:200:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &op);
         ~~~~~^~~~~~~~~~~
sterilizing.cpp:204:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &pos, &val);
             ~~~~~^~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:212:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &st, &dr);
             ~~~~~^~~~~~~~~~~~~~~~~~
sterilizing.cpp:220:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &st, &dr);
             ~~~~~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...