| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 92543 |
2019-01-03T11:31:23 Z |
Retro3014 |
Sails (IOI07_sails) |
C++17 |
|
1000 ms |
8800 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{
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, 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, (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;
}
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[idx].lazy=0;
}
}
void update(int idx, int x, int y){
calc1(idx);
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++; 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].l].min);
}
int min(int idx, int x, int y){
calc1(idx);
if(seg[idx].s>y || seg[idx].e<x) return INF;
if(seg[idx].s>=x && seg[idx].e<=y) return seg[idx].min;
return min(min(seg[idx].l, x, y), min(seg[idx].r, x, y));
}
int max(int idx, int x, int y){
calc1(idx);
if(seg[idx].s>y || seg[idx].e<x) return 0;
if(seg[idx].s>=x && seg[idx].e<=y) return seg[idx].max;
return max(max(seg[idx].l, x, y), max(seg[idx].r, x, y));
}
int find_l(int x, int y, int t){
int s=x, e=y, mid;
while(s<e){
mid=(s+e)/2;
if(max(0, 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(min(0, x, mid)==t){
s=mid;
}else e=mid-1;
}
return s;
}
int main(){
//freopen("in.txt", "r", stdin);
scanf("%d", &N);
seg.push_back({0, 0, 0, 1, 100000, -1, -1});
init();
for(int i=1; i<=N; i++){
int a, b;
scanf("%d%d", &a, &b);m.push_back({a, b});
}sort(m.begin(), m.end());
int l, r, s, e, t;
for(int i=0; i<N; i++){
e=m[i].h; s=m[i].h-m[i].k+1;
t=max(0, s, 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);
update(0, l, l+r-s);
update(0, r+1, e);
}
ll ans=0;
for(int i=1; i<=100000; i++){
ll t=(ll)max(0, i, i);
printf("%lld\n", t);
ans+=t*(t-1)/2;
}
printf("%lld", ans);
return 0;
}
Compilation message
sails.cpp: In function 'int main()':
sails.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
sails.cpp:117: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 |
Incorrect |
43 ms |
7784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
7788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
7788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
7788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
7784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
140 ms |
7784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
220 ms |
7788 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
726 ms |
7808 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1084 ms |
8416 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1081 ms |
8672 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1071 ms |
8800 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
