이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "prize.h"
#include <vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
#define MX 202300
int n,m,l,r,mx,mid,x;
vector<int>c;
struct Tree
{
#define ls x*2
#define rs x*2+1
int s[MX<<2];
void push_up(int x)
{
s[x]=s[ls]+s[rs];
return;
}
void build(int x,int l,int r)
{
s[x]=0;
if(l==r)return;
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
return;
}
void add(int x,int l,int r,int y)
{
if(l==r){
s[x]++;
return;
}
int mid=l+r>>1;
if(y<=mid)add(ls,l,mid,y);
else add(rs,mid+1,r,y);
push_up(x);
return;
}
int ask(int x,int L,int R,int l,int r)
{
if(L==l&&R==r)return s[x];
int mid=L+R>>1;
if(r<=mid)return ask(ls,L,mid,l,r);
else if(l>mid)return ask(rs,mid+1,R,l,r);
else return ask(ls,L,mid,l,mid)+ask(rs,mid+1,R,mid+1,r);
}
int askk(int x,int l,int r,int k)
{
if(l==r)return l;
int mid=l+r>>1;
if(mid-l+1-s[ls]>=k)return askk(ls,l,mid,k);
else return askk(rs,mid+1,r,k-(mid-l+1-s[ls]));
}
}T;
int find_best(int N) {
n=N;
mx=0;
for(int i=1;i<=min(500,n);++i){
c=ask(i-1);
mx=max(mx,c[0]+c[1]);
}
m=n;
T.build(1,1,n);
while(1<=m){
l=1;r=m;
while(l<r){
mid=l+r+1>>1;
x=T.askk(1,1,n,mid);
c=ask(x-1);
if(c[0]+c[1]!=mx){
l=mid;
break;
}
if(c[0]>T.ask(1,1,n,1,x-1))r=mid-1;
else l=mid;
}
x=T.askk(1,1,n,l);
if(c[0]+c[1]==0)return x-1;
T.add(1,1,n,x);
m--;
}
}
컴파일 시 표준 에러 (stderr) 메시지
prize.cpp: In member function 'void Tree::build(int, int, int)':
prize.cpp:32:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
32 | int mid=l+r>>1;
| ~^~
prize.cpp: In member function 'void Tree::add(int, int, int, int)':
prize.cpp:43:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int mid=l+r>>1;
| ~^~
prize.cpp: In member function 'int Tree::ask(int, int, int, int, int)':
prize.cpp:52:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | int mid=L+R>>1;
| ~^~
prize.cpp: In member function 'int Tree::askk(int, int, int, int)':
prize.cpp:60:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
60 | int mid=l+r>>1;
| ~^~
prize.cpp: In function 'int find_best(int)':
prize.cpp:77:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
77 | mid=l+r+1>>1;
| ~~~^~
prize.cpp:92:1: warning: control reaches end of non-void function [-Wreturn-type]
92 | }
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |