| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1019477 | boyliguanhan | Sails (IOI07_sails) | C++17 | 135 ms | 8540 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
struct segtree{
struct node{
long long sum,mn,lz;
node(){mn=sum=lz=0;}
} T[1<<18];
void pd(int i,int sz){
T[i].mn+=T[i].lz;
T[i].sum+=sz*T[i].lz;
if(sz>1)T[i*2].lz+=T[i].lz,
T[i*2+1].lz+=T[i].lz;
T[i].lz=0;
}
int walk(int i,int l,int r,int p){
if(l==r)return l;
pd(i*2,r-l+2>>1),pd(i*2+1,r-l+1>>1);
if(p>=T[i*2].mn)
return walk(i*2,l,l+r>>1,p);
return walk(i*2+1,l+r+2>>1,r,p);
}
int atpos(int i,int l,int r,int p){
pd(i,r-l+1);if(l==r)return T[i].mn;
if(l+r>>1<p)
return atpos(i*2+1,l+r+2>>1,r,p);
else return atpos(i*2,l,l+r>>1,p);
}
long long query(int i,int l,int r,int ll,int rr){
pd(i,r-l+1);
if(ll>r||l>rr) return 0;
if(ll<=l&&r<=rr)
return T[i].lz++,pd(i,r-l+1),T[i].sum;
long long ans=query(i*2,l,l+r>>1,ll,rr)+
query(i*2+1,l+r+2>>1,r,ll,rr);
T[i].mn=min(T[i*2].mn,T[i*2+1].mn);
T[i].sum=T[i*2].sum+T[i*2+1].sum;
return ans;
}
segtree(){T[1].lz=-1;}
} ST;
int main(){
cin.tie(0)->sync_with_stdio(0);
int n;
long long ans=0;
cin>>n;
vector<pair<int,int>>masts(n);
for(auto&[h,k]:masts)
cin>>h>>k;
sort(masts.begin(),masts.end());
for(auto[h,k]:masts){
int y=ST.atpos(1,1,1e5+1,h-k+1);
int posl=ST.walk(1,1,1e5+1,y-1);
int posr=ST.walk(1,1,1e5+1,y);
ans+=ST.query(1,1,1e5+1,posl,h);
k-=max(0,h-posl+1);
ans+=ST.query(1,1,1e5+1,posr,posr+k-1);
}
cout<<ans<<'\n';
}컴파일 시 표준 에러 (stderr) 메시지
| # | 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... | ||||
| # | 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... | ||||
