Submission #298960

#	Time	Username	Problem	Language	Result	Execution time	Memory
298960		TadijaSebez	새로운 문제 (POI13_kon)	C++11	100 / 100	793 ms	27896 KiB

kon

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10