이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define DIMN 1000010
using namespace std;
struct segm{
int maxi , pmaxi , sorted , maxi2 , pmaxi2;
} aint[4 * DIMN];
int v[DIMN];
void build (int nod , int st , int dr){
int mid = (st + dr)/2;
if (st == dr){
aint[nod].maxi = v[st];
aint[nod].pmaxi = st;
aint[nod].maxi2 = -1;
aint[nod].pmaxi2 = DIMN + 10;
aint[nod].sorted = 1;
return;
}
build (2 * nod , st , mid);
build (2 * nod + 1 , mid + 1 , dr);
if (aint[2 * nod].maxi >= aint[2 * nod + 1].maxi){
aint[nod].maxi = aint[2 * nod].maxi;
aint[nod].pmaxi = aint[2 * nod].pmaxi;
if (aint[2 * nod].maxi2 >= aint[2 * nod + 1].maxi){
aint[nod].maxi2 = aint[2 * nod].maxi2;
aint[nod].pmaxi2 = aint[2 * nod].pmaxi2;
}
else {
aint[nod].maxi2 = aint[2 * nod + 1].maxi;
aint[nod].pmaxi2 = aint[2 * nod + 1].pmaxi;
}
}
else {
aint[nod].maxi = aint[2 * nod + 1].maxi;
aint[nod].pmaxi = aint[2 * nod + 1].pmaxi;
aint[nod].maxi2 = aint[2 * nod + 1].maxi2;
aint[nod].pmaxi2 = aint[2 * nod + 1].pmaxi2;
}
/// sorted ins daca intervalul l .. r este crescator oricum
if (aint[2 * nod].sorted && aint[2 * nod + 1].sorted && v[mid] <= v[mid + 1])
aint[nod].sorted = 1;
else aint[nod].sorted = 0;
}
int qsuff (int nod , int st , int dr , int l , int r){
int mid = (st + dr) / 2 , sum = 0;
if (l <= st && dr <= r){
if (aint[nod].sorted)
return st - dr + 1;
sum = qsuff (2 * nod + 1 , mid + 1 , dr , l , r);
if (sum == min(r , dr) - (mid + 1) + 1 && v[mid] <= v[mid + 1])
sum += qsuff(2 * nod , st , mid , l , r);
return sum;
}
if (mid + 1 <= r)
sum = qsuff (2 * nod + 1 , mid + 1 , dr , l , r);
if (l <= mid && (mid + 1 > r || (sum == min(r , dr) - (mid + 1) + 1 && v[mid] <= v[mid + 1])))
sum += qsuff(2 * nod , st , mid , l , r);
return sum;
}
int maxi , pmaxi , maxi2 , pmaxi2;
void qmaxi (int nod , int st , int dr , int l , int r){
int mid = (st + dr) / 2;
if (l <= st && dr <= r){
if (maxi < aint[nod].maxi){
maxi = aint[nod].maxi;
pmaxi = aint[nod].pmaxi;
maxi2 = aint[nod].maxi2;
pmaxi2 = aint[nod].pmaxi2;
}
else if (maxi2 < aint[nod].maxi){
maxi2 = aint[nod].maxi;
pmaxi2 = aint[nod].pmaxi;
}
return;
}
if (l <= mid)
qmaxi(2 * nod , st , mid , l , r);
if (mid + 1 <= r)
qmaxi (2 * nod + 1 , mid + 1 , dr , l , r);
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n , q , i , l , r , k , suff , a , b , st , dr , mid;
fscanf (fin,"%d%d",&n,&q);
for (i = 1 ; i <= n ; i++){
fscanf (fin,"%d",&v[i]);
}
build (1 , 1 , n);
for (;q;q--){
fscanf (fin,"%d%d%d", &l , &r , &k);
suff = qsuff (1 , 1 , n , l , r);
r = r - suff;
if (r < l){
fprintf (fout,"1\n");
continue;
}
/// acum intre l si r exista clar niste inversiuni
maxi = -1;
pmaxi = n + 1;
maxi2 = -1;
pmaxi2 = n + 1;
qmaxi (1 , 1 , n , l , r);
a = maxi;
b = maxi2;
st = r + 1;
dr = r + suff; /// cauti cel mai mare element mai mic decat a
while (st <= dr){
mid = (st + dr) / 2;
if ( a >= v[mid] )
dr = mid - 1;
else st = mid + 1;
}
if (st >= r + 1 && v[st] > b){
b = v[st];
}
fprintf (fout,"%d\n", (a + b <= k) );
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:121:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
121 | fscanf (fin,"%d%d",&n,&q);
| ~~~~~~~^~~~~~~~~~~~~~~~~~
sortbooks.cpp:123:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
123 | fscanf (fin,"%d",&v[i]);
| ~~~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:129:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
129 | fscanf (fin,"%d%d%d", &l , &r , &k);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |