oj.uz

Submission #298960

# Submission time Handle Problem Language Result Execution time Memory
298960 2020-09-14T11:14:56 Z TadijaSebez Watering can (POI13_kon) C++11
100 / 100
 793 ms 27896 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=300050;
int bit[N],k,n;
void Set(int i){for(;i<N;i+=i&-i)bit[i]++;}
int Get(int i){int ans=0;for(;i;i-=i&-i)ans+=bit[i];return ans;}
const int M=2*N;
const int inf=1e9+7;
#define pii pair<int,int>
int ls[M],rs[M],tsz,root,lzy[M];
pii mn[M];
void Set(int&c,int ss,int se,int qi,int f){
	if(!c)c=++tsz;
	if(ss==se){mn[c]={f,ss};return;}
	int mid=ss+se>>1;
	if(qi<=mid)Set(ls[c],ss,mid,qi,f);
	else Set(rs[c],mid+1,se,qi,f);
	mn[c]=min(mn[ls[c]],mn[rs[c]]);
	mn[c].first+=lzy[c];
}
void Add(int c,int ss,int se,int qs,int qe,int f){
	if(qs>qe||qs>se||ss>qe)return;
	if(qs<=ss&&qe>=se){lzy[c]+=f;mn[c].first+=f;return;}
	int mid=ss+se>>1;
	Add(ls[c],ss,mid,qs,qe,f);
	Add(rs[c],mid+1,se,qs,qe,f);
	mn[c]=min(mn[ls[c]],mn[rs[c]]);
	mn[c].first+=lzy[c];
}
void inicjuj(int n,int k,int*D){
	::n=n;::k=k;
	for(int i=0;i<n;i++){
		if(D[i]>=k)Set(i+1),Set(root,1,n,i+1,inf);
		else Set(root,1,n,i+1,k-D[i]);
	}
}

void podlej(int a,int b){
	Add(root,1,n,a+1,b+1,-1);
	while(mn[root].first==0){
		Set(mn[root].second);
		Set(root,1,n,mn[root].second,inf);
	}
}

int dojrzale(int a,int b){
	return Get(b+1)-Get(a);
}

Compilation message

kon.cpp: In function 'void Set(int&, int, int, int, int)':
kon.cpp:15:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |  int mid=ss+se>>1;
      |          ~~^~~
kon.cpp: In function 'void Add(int, int, int, int, int, int)':
kon.cpp:24:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |  int mid=ss+se>>1;
      |          ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 3576 KB Output is correct
2 Correct 66 ms 3072 KB Output is correct
3 Correct 51 ms 2996 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 4472 KB Output is correct
2 Correct 131 ms 5056 KB Output is correct
3 Correct 115 ms 4868 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 7860 KB Output is correct
2 Correct 128 ms 6904 KB Output is correct
3 Correct 153 ms 6904 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 13312 KB Output is correct
2 Correct 172 ms 9464 KB Output is correct
3 Correct 238 ms 11128 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 13688 KB Output is correct
2 Correct 325 ms 13168 KB Output is correct
3 Correct 256 ms 13432 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 20856 KB Output is correct
2 Correct 603 ms 19320 KB Output is correct
3 Correct 423 ms 22136 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 793 ms 26524 KB Output is correct
2 Correct 537 ms 26216 KB Output is correct
3 Correct 552 ms 25208 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 682 ms 27548 KB Output is correct
2 Correct 512 ms 27896 KB Output is correct
3 Correct 445 ms 26104 KB Output is correct