| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 92562 |
2019-01-03T12:16:34 Z |
Retro3014 |
Sails (IOI07_sails) |
C++17 |
|
1000 ms |
11996 KB |
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;
#define MAX_N 100000
#define INF 100000
typedef long long ll;
struct S{
ll sum;
int min, max, lazy;
int s, e;
int l, r;
};
vector<S> seg;
int N;
struct M{
int h, k;
bool operator <(const M &a)const{
return h<a.h;
}
};
vector<M> m;
deque<int> dq;
void init(){
dq.push_back(0);
int x=0;
while(!dq.empty()){
x=dq.front(); dq.pop_front();
if(seg[x].s!=seg[x].e){
if(seg[x].l==-1){
seg[x].l=(int)seg.size();
seg.push_back({0, 0, 0, 0, seg[x].s, (seg[x].s+seg[x].e)/2, -1, -1});
dq.push_back(seg[x].l);
}
if(seg[x].r==-1){
seg[x].r=(int)seg.size();
seg.push_back({0, 0, 0, 0, (seg[x].s+seg[x].e)/2+1, seg[x].e, -1, -1});
dq.push_back(seg[x].r);
}
}
}
}
void calc1(int idx){
if(seg[idx].lazy>0){
if(seg[idx].l!=-1){
seg[seg[idx].l].max+=seg[idx].lazy; seg[seg[idx].l].min+=seg[idx].lazy; seg[seg[idx].l].lazy+=seg[idx].lazy;
seg[seg[idx].l].sum+=(ll)(seg[seg[idx].l].e-seg[seg[idx].l].s+1) * seg[idx].lazy;
}
if(seg[idx].r!=-1){
seg[seg[idx].r].max+=seg[idx].lazy; seg[seg[idx].r].min+=seg[idx].lazy; seg[seg[idx].r].lazy+=seg[idx].lazy;
seg[seg[idx].r].sum+=(ll)(seg[seg[idx].r].e-seg[seg[idx].r].s+1) * seg[idx].lazy;
}
seg[idx].lazy=0;
}
}
void update(int idx, int x, int y){
if(seg[idx].lazy>0){
if(seg[idx].l!=-1){
seg[seg[idx].l].max+=seg[idx].lazy; seg[seg[idx].l].min+=seg[idx].lazy; seg[seg[idx].l].lazy+=seg[idx].lazy;
seg[seg[idx].l].sum+=(ll)(seg[seg[idx].l].e-seg[seg[idx].l].s+1) * seg[idx].lazy;
}
if(seg[idx].r!=-1){
seg[seg[idx].r].max+=seg[idx].lazy; seg[seg[idx].r].min+=seg[idx].lazy; seg[seg[idx].r].lazy+=seg[idx].lazy;
seg[seg[idx].r].sum+=(ll)(seg[seg[idx].r].e-seg[seg[idx].r].s+1) * seg[idx].lazy;
}
seg[idx].lazy=0;
}
if(seg[idx].s>y || seg[idx].e<x) return;
if(seg[idx].s>=x && seg[idx].e<=y) {
seg[idx].lazy++; seg[idx].max++; seg[idx].min++; seg[idx].sum+=(ll)(seg[idx].e-seg[idx].s+1); return;
}
update(seg[idx].l, x, y);
update(seg[idx].r, x, y);
seg[idx].max=max(seg[seg[idx].l].max, seg[seg[idx].r].max);
seg[idx].min=min(seg[seg[idx].l].min, seg[seg[idx].r].min);
seg[idx].sum=seg[seg[idx].l].sum+seg[seg[idx].r].sum;
}
int mini(int x, int y){
dq.push_back(0); int idx, ret=INF;
while(!dq.empty()){
idx=dq.front(); dq.pop_front();
if(seg[idx].lazy>0){
if(seg[idx].l!=-1){
seg[seg[idx].l].max+=seg[idx].lazy; seg[seg[idx].l].min+=seg[idx].lazy; seg[seg[idx].l].lazy+=seg[idx].lazy;
seg[seg[idx].l].sum+=(ll)(seg[seg[idx].l].e-seg[seg[idx].l].s+1) * seg[idx].lazy;
}
if(seg[idx].r!=-1){
seg[seg[idx].r].max+=seg[idx].lazy; seg[seg[idx].r].min+=seg[idx].lazy; seg[seg[idx].r].lazy+=seg[idx].lazy;
seg[seg[idx].r].sum+=(ll)(seg[seg[idx].r].e-seg[seg[idx].r].s+1) * seg[idx].lazy;
}
seg[idx].lazy=0;
}
if(!(seg[idx].s>y || seg[idx].e<x)){
if(seg[idx].s>=x && seg[idx].e<=y) ret=min(ret, seg[idx].min);
else{dq.push_back(seg[idx].l); dq.push_back(seg[idx].r);}
}
}
return ret;
}
int maxi(int x, int y){
dq.push_back(0); int ret=0, idx;
while(!dq.empty()){
idx=dq.front(); dq.pop_front();
if(seg[idx].lazy>0){
if(seg[idx].l!=-1){
seg[seg[idx].l].max+=seg[idx].lazy; seg[seg[idx].l].min+=seg[idx].lazy; seg[seg[idx].l].lazy+=seg[idx].lazy;
seg[seg[idx].l].sum+=(ll)(seg[seg[idx].l].e-seg[seg[idx].l].s+1) * seg[idx].lazy;
}
if(seg[idx].r!=-1){
seg[seg[idx].r].max+=seg[idx].lazy; seg[seg[idx].r].min+=seg[idx].lazy; seg[seg[idx].r].lazy+=seg[idx].lazy;
seg[seg[idx].r].sum+=(ll)(seg[seg[idx].r].e-seg[seg[idx].r].s+1) * seg[idx].lazy;
}
seg[idx].lazy=0;
}
if(!(seg[idx].s>y || seg[idx].e<x)){
if(seg[idx].s>=x && seg[idx].e<=y) ret=max(ret, seg[idx].max);
else{
dq.push_back(seg[idx].l); dq.push_back(seg[idx].r);
}
}
}
return ret;
}
ll sum(int idx, int x, int y){
if(seg[idx].lazy>0){
if(seg[idx].l!=-1){
seg[seg[idx].l].max+=seg[idx].lazy; seg[seg[idx].l].min+=seg[idx].lazy; seg[seg[idx].l].lazy+=seg[idx].lazy;
seg[seg[idx].l].sum+=(ll)(seg[seg[idx].l].e-seg[seg[idx].l].s+1) * seg[idx].lazy;
}
if(seg[idx].r!=-1){
seg[seg[idx].r].max+=seg[idx].lazy; seg[seg[idx].r].min+=seg[idx].lazy; seg[seg[idx].r].lazy+=seg[idx].lazy;
seg[seg[idx].r].sum+=(ll)(seg[seg[idx].r].e-seg[seg[idx].r].s+1) * seg[idx].lazy;
}
seg[idx].lazy=0;
}
if(seg[idx].s>y || seg[idx].e<x) return 0;
if(seg[idx].s>=x && seg[idx].e<=y) return seg[idx].sum;
return sum(seg[idx].l, x, y)+sum(seg[idx].r, x, y);
}
int get(int x){
dq.push_back(0);
int idx=0;
while(!dq.empty()){
idx=dq.front(); dq.pop_front();
if(seg[idx].lazy>0){
if(seg[idx].l!=-1){
seg[seg[idx].l].max+=seg[idx].lazy; seg[seg[idx].l].min+=seg[idx].lazy; seg[seg[idx].l].lazy+=seg[idx].lazy;
seg[seg[idx].l].sum+=(ll)(seg[seg[idx].l].e-seg[seg[idx].l].s+1) * seg[idx].lazy;
}
if(seg[idx].r!=-1){
seg[seg[idx].r].max+=seg[idx].lazy; seg[seg[idx].r].min+=seg[idx].lazy; seg[seg[idx].r].lazy+=seg[idx].lazy;
seg[seg[idx].r].sum+=(ll)(seg[seg[idx].r].e-seg[seg[idx].r].s+1) * seg[idx].lazy;
}
seg[idx].lazy=0;
}
if(seg[idx].s==seg[idx].e) return seg[idx].max;
if((seg[idx].s+seg[idx].e)/2>=x){
dq.push_back(seg[idx].l);
}else dq.push_back(seg[idx].r);
}
return 0;
}
int find_l(int x, int y, int t){
int s=x, e=y, mid;
while(s<e){
mid=(s+e)/2;
if(maxi(mid, y)==t){
e=mid;
}else{
s=mid+1;
}
}
return s;
}
int find_r(int x, int y, int t){
int s=x, e=y, mid;
while(s<e){
mid=(s+e)/2+1;
if(mini(x, mid)==t){
s=mid;
}else e=mid-1;
}
return s;
}
int main(){
//freopen("in.txt", "r", stdin);
scanf("%d", &N);
int MH=0;
for(int i=1; i<=N; i++){
int a, b;
scanf("%d%d", &a, &b);m.push_back({a, b});
MH=max(MH, a);
}sort(m.begin(), m.end());
seg.push_back({0, 0, 0, 0, 1, MH, -1, -1});
init();
int l, r, s, e, t;
ll ans=0;
for(int i=0; i<N; i++){
e=m[i].h; s=m[i].h-m[i].k+1;
ans+=sum(0, s, e);
t=get(s);
l=find_l(1, s, t);
r=find_r(s, e, t);
//printf("%d %d %d %d %d\n", s, e, l, r, t);
if(l==s) update(0, s, e);
else{
update(0, l, l+r-s);
update(0, r+1, e);
}
}
printf("%lld\n", ans);
return 0;
}
Compilation message
sails.cpp: In function 'int main()':
sails.cpp:203:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
sails.cpp:207:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);m.push_back({a, b});
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
376 KB |
Output is correct |
| 2 |
Correct |
1 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
376 KB |
Output is correct |
| 2 |
Correct |
1 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
828 KB |
Output is correct |
| 2 |
Correct |
32 ms |
10848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
104 ms |
3084 KB |
Output is correct |
| 2 |
Correct |
238 ms |
1112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
197 ms |
3308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
703 ms |
6180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1084 ms |
11868 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1087 ms |
11988 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1076 ms |
11996 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
