이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define kyou using
#define mo namespace
#define kawaii std
kyou mo kawaii; // hi honey~
#define ll long long
#define ld long double
// #define endl "\n"
const int MX = 400005;
const int LG = 5;
const int BLOCK = 205;
const int inf = 1000000069;
const ll inf_ll = 8000000000000000069ll;
const ll mod = 1e9 + 7;
const int dxh[] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dyh[] = {2, -2, 2, -2, 1, -1, 1, -1}; // horse
const int dx[] = {0, 1, 0, -1, 0, 0};
const int dy[] = {1, 0, -1, 0, 0, 0}; // adj
const int dz[] = {0, 0, 0, 0, 1, -1}; // 3d
const int dxd[] = {1, 1, 1, 0, -1, -1, -1, 0};
const int dyd[] = {1, 0, -1, -1, -1, 0, 1, 1}; // diag
#define min(x, y) (x < y ? x : y)
#define max(x, y) (x > y ? x : y)
bool untied = 0;
void setIn(string s){freopen(s.c_str(), "r", stdin);}
void setOut(string s){freopen(s.c_str(), "w", stdout);}
void unsyncIO(){cin.tie(0) -> sync_with_stdio(0);}
void setIO(string s = ""){
if(!untied) unsyncIO(), untied = 1;
if(s.size()){
setIn(s + ".in");
setOut(s + "_output.out");
}
}
const int H = (1 << 19) - 1;
ll key[H + 1];
int val[H + 1];
int &last(ll k){
int i = (int)(k & H);
while(val[i] != 0 && key[i] != k)
i = (i + 1) & H;
key[i] = k;
return val[i];
}
int n, q;
ll v[MX];
int anc[MX][LG], pw10[LG + 1];
int main(){
pw10[0] = 1;
for(int i = 1; i <= LG; i ++)
pw10[i] = pw10[i - 1] * 10;
cin.tie(0) -> sync_with_stdio(0);
cin >> n;
for(int i = 1; i <= n; i ++)
cin >> v[i];
for(int i = 1; i <= n; i ++)
v[i] += v[i - 1];
last(v[n]) = n;
anc[n][0] = n + 1;
for(int i = n - 1; i >= 0; i --){
int &tp = last(v[i]);
if(tp && tp < anc[i + 1][0]) anc[i][0] = tp;
else anc[i][0] = anc[i + 1][0];
tp = i;
}
for(int j = 1; j < LG; j ++){
for(int i = 0; i <= n; i ++){
if(anc[i][j - 1] == n + 1) anc[i][j] = n + 1;
else if(anc[anc[i][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
else if(anc[anc[anc[i][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
else if(anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
else if(anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
else if(anc[anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
else if(anc[anc[anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
else if(anc[anc[anc[anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
else if(anc[anc[anc[anc[anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
else anc[i][j] = anc[anc[anc[anc[anc[anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1];
}
}
cin >> q;
for(int l, r, i = 0; i < q; i ++){
cin >> l >> r;
l --;
int ans = 0, nw = l;
for(int j = LG; j >= 0; j --){
for(int tp = 0; tp < 10; tp ++){
if(j == LG){
int cr;
if(anc[nw][j - 1] == n + 1) cr = n + 1;
else if(anc[anc[nw][j - 1]][j - 1] == n + 1) cr = n + 1;
else if(anc[anc[anc[nw][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1;
else if(anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1;
else if(anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1;
else if(anc[anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1;
else if(anc[anc[anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1;
else if(anc[anc[anc[anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1;
else if(anc[anc[anc[anc[anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1;
else cr = anc[anc[anc[anc[anc[anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1];
if(cr <= r){
ans += pw10[j];
nw = cr;
}
}else{
if(anc[nw][j] <= r){
ans += pw10[j];
nw = anc[nw][j];
}else break;
}
}
}
cout << ans << endl;
}
}
컴파일 시 표준 에러 (stderr) 메시지
sumzero.cpp: In function 'void setIn(std::string)':
sumzero.cpp:29:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
29 | void setIn(string s){freopen(s.c_str(), "r", stdin);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sumzero.cpp: In function 'void setOut(std::string)':
sumzero.cpp:30:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | void setOut(string s){freopen(s.c_str(), "w", stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |