이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "weirdtree.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define elif else if
#define ep insert
using namespace std;
struct node{
ll mx1,mx2,sum,f;
};
const int NN=3e5+5;
ll n,a[NN];
node seg[4*NN+5];
map<int,set<int>> mp;
node merge(node x,node y){
int a[4]={x.mx1,x.mx2,y.mx1,y.mx2};
sort(a,a+4);
node z;
z.mx1=a[3];
if (a[2]==a[3]) z.mx2=a[1];
else z.mx2=a[2];
z.sum=x.sum+y.sum;
if (a[2]==a[3]) z.f=x.f+y.f;
elif (x.mx1>y.mx1) z.f=x.f;
else z.f=y.f;
return z;
}
void build(int x,int l,int r){
if (l==r){
seg[x]={a[l],0,a[l],1};
return;
}int mid=(l+r)/2;
build(x*2,l,mid);
build(x*2+1,mid+1,r);
seg[x]=merge(seg[x*2],seg[x*2+1]);
return;
}
void edit(int x,int l,int r,int idx){
if (l==r){
seg[x]={a[l],0,a[l],1};
return;
}int mid=(l+r)/2;
if (idx<=mid) edit(x*2,l,mid,idx);
else edit(x*2+1,mid+1,r,idx);
seg[x]=merge(seg[x*2],seg[x*2+1]);
return;
}
node query(int x,int l,int r,int lx,int rx){
if (l>=lx && r<=rx) return seg[x];
if (l>rx || r<lx) return {INT_MIN,INT_MIN,0,0};
int mid=(l+r)/2;
return merge(query(x*2,l,mid,lx,rx),query(x*2+1,mid+1,r,lx,rx));
}
void initialise(int N, int Q, int h[]) {
n=N;
for (int i=1;i<=n;i++) a[i]=h[i],mp[a[i]].ep(i);
build(1,1,n);
return;
}
void cut(int l, int r, int kk) {
ll k=kk;
while (k>0){
node x=query(1,1,n,l,r);
ll mx1=x.mx1,mx2=x.mx2,f=x.f,d=(mx1-mx2);
if (!mx1) break;
if (k>=d*f){
while (true){
auto it=mp[mx1].lower_bound(l);
if (it==mp[mx1].end() || *it>r) break;
int i=*it;
mp[mx1].erase(it);
mp[mx2].ep(i);
a[i]=mx2;
edit(1,1,n,i);
}
k-=d*f;
continue;
}
int s=k/f+1;
for (int i=0;i<k%f;i++){
int j=*mp[mx1].lower_bound(l);
mp[mx1].erase(j);
mp[mx1-s].ep(j);
a[j]-=s;
edit(1,1,n,j);
}
s=k/f;
while (s){
auto it=mp[mx1].lower_bound(l);
if (it==mp[mx1].end()) break;
if (*it>r) break;
int j=*it;
mp[mx1].erase(it);
mp[mx1-s].ep(j);
a[j]-=s;
edit(1,1,n,j);
}break;
}
//for (int i=1;i<=n;i++) cout<<a[i]<<' ';
//cout<<endl;
return;
}
void magic(int i, int x) {
return;
}
long long int inspect(int l, int r) {
return query(1,1,n,l,r).sum;
}
컴파일 시 표준 에러 (stderr) 메시지
weirdtree.cpp: In function 'node merge(node, node)':
weirdtree.cpp:16:17: warning: narrowing conversion of 'x.node::mx1' from 'long long int' to 'int' [-Wnarrowing]
16 | int a[4]={x.mx1,x.mx2,y.mx1,y.mx2};
| ~~^~~
weirdtree.cpp:16:23: warning: narrowing conversion of 'x.node::mx2' from 'long long int' to 'int' [-Wnarrowing]
16 | int a[4]={x.mx1,x.mx2,y.mx1,y.mx2};
| ~~^~~
weirdtree.cpp:16:29: warning: narrowing conversion of 'y.node::mx1' from 'long long int' to 'int' [-Wnarrowing]
16 | int a[4]={x.mx1,x.mx2,y.mx1,y.mx2};
| ~~^~~
weirdtree.cpp:16:35: warning: narrowing conversion of 'y.node::mx2' from 'long long int' to 'int' [-Wnarrowing]
16 | int a[4]={x.mx1,x.mx2,y.mx1,y.mx2};
| ~~^~~
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |