oj.uz

Submission #1113151

# Submission time Handle Problem Language Result Execution time Memory
1113151 2024-11-15T22:57:55 Z StefanSebez Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
0 / 100
 2558 ms 134672 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e6+50;
const ll inf=1e16;
vector<array<int,3>>Qs[N];
int res[N],a[N];
int root,nc,lc[2*N],rc[2*N];
ll maks[2*N],lazy[2*N];
void update(int &c,ll x){if(!c)c=++nc;maks[c]+=x;lazy[c]+=x;}
void push(int &c){update(lc[c],lazy[c]),update(rc[c],lazy[c]);lazy[c]=0;}
void Update(int &c,int ss,int se,int qs,int qe,ll x){
	if(!c)c=++nc;
	if(qs>qe||qe<ss||se<qs)return;
	if(qs<=ss&&se<=qe){update(c,x);return;}
	int mid=ss+se>>1;push(c);
	Update(lc[c],ss,mid,qs,qe,x),Update(rc[c],mid+1,se,qs,qe,x);
	maks[c]=max(maks[lc[c]],maks[rc[c]]);
}
ll Get(int &c,int ss,int se,int qs,int qe){
	if(!c)c=++nc;
	if(qs>qe||qe<ss||se<qs)return -inf;
	if(qs<=ss&&se<=qe)return maks[c];
	int mid=ss+se>>1;push(c);
	return max(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
}
int main(){
    int n,q;scanf("%i%i",&n,&q);
    for(int i=1;i<=n;i++) scanf("%i",&a[i]);
    for(int i=1,l,r,k;i<=q;i++) scanf("%i%i%i",&l,&r,&k),Qs[l].pb({r,k,i});
    maks[0]=-inf;
    for(int i=1;i<=n;i++) Update(root,1,n,i,i,a[i]);
    vector<int>mono={n+1};
    for(int i=n;i>=1;i--){
		while(mono.size()>1&&a[mono.back()]<=a[i]){
			int prosli=mono.back();mono.pop_back();
			Update(root,1,n,prosli,mono.back()-1,-a[prosli]);
			Update(root,1,n,prosli,prosli,inf);
		}
		Update(root,1,n,i,mono.back()-1,a[i]);
		mono.pb(i);
		Update(root,1,n,i,i,-inf);
		for(auto j:Qs[i]){
			int x=Get(root,1,n,i,j[0]);
			//printf("%i %i: %i\n",i,j[0],x);
			if(x<=j[1]) res[j[2]]=1;
		}
    }
    for(int i=1;i<=q;i++) printf("%i\n",res[i]);
    return 0;
}

Compilation message

sortbooks.cpp: In function 'void Update(int&, int, int, int, int, long long int)':
sortbooks.cpp:20:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |  int mid=ss+se>>1;push(c);
      |            ^
sortbooks.cpp: In function 'long long int Get(int&, int, int, int, int)':
sortbooks.cpp:28:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |  int mid=ss+se>>1;push(c);
      |            ^
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:32:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     int n,q;scanf("%i%i",&n,&q);
      |             ~~~~~^~~~~~~~~~~~~~
sortbooks.cpp:33:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     for(int i=1;i<=n;i++) scanf("%i",&a[i]);
      |                           ~~~~~^~~~~~~~~~~~
sortbooks.cpp:34:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     for(int i=1,l,r,k;i<=q;i++) scanf("%i%i%i",&l,&r,&k),Qs[l].pb({r,k,i});
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25168 KB Output is correct
2 Correct 11 ms 25168 KB Output is correct
3 Correct 19 ms 25168 KB Output is correct
4 Correct 17 ms 25168 KB Output is correct
5 Correct 17 ms 25252 KB Output is correct
6 Correct 18 ms 25168 KB Output is correct
7 Correct 17 ms 25168 KB Output is correct
8 Correct 18 ms 25184 KB Output is correct
9 Correct 18 ms 25168 KB Output is correct
10 Incorrect 20 ms 25168 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25168 KB Output is correct
2 Correct 11 ms 25168 KB Output is correct
3 Correct 19 ms 25168 KB Output is correct
4 Correct 17 ms 25168 KB Output is correct
5 Correct 17 ms 25252 KB Output is correct
6 Correct 18 ms 25168 KB Output is correct
7 Correct 17 ms 25168 KB Output is correct
8 Correct 18 ms 25184 KB Output is correct
9 Correct 18 ms 25168 KB Output is correct
10 Incorrect 20 ms 25168 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2524 ms 131392 KB Output is correct
2 Correct 2558 ms 132432 KB Output is correct
3 Correct 2486 ms 134356 KB Output is correct
4 Incorrect 2531 ms 134672 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 218 ms 34888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25168 KB Output is correct
2 Correct 11 ms 25168 KB Output is correct
3 Correct 19 ms 25168 KB Output is correct
4 Correct 17 ms 25168 KB Output is correct
5 Correct 17 ms 25252 KB Output is correct
6 Correct 18 ms 25168 KB Output is correct
7 Correct 17 ms 25168 KB Output is correct
8 Correct 18 ms 25184 KB Output is correct
9 Correct 18 ms 25168 KB Output is correct
10 Incorrect 20 ms 25168 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25168 KB Output is correct
2 Correct 11 ms 25168 KB Output is correct
3 Correct 19 ms 25168 KB Output is correct
4 Correct 17 ms 25168 KB Output is correct
5 Correct 17 ms 25252 KB Output is correct
6 Correct 18 ms 25168 KB Output is correct
7 Correct 17 ms 25168 KB Output is correct
8 Correct 18 ms 25184 KB Output is correct
9 Correct 18 ms 25168 KB Output is correct
10 Incorrect 20 ms 25168 KB Output isn't correct
11 Halted 0 ms 0 KB -