| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 92811 |
2019-01-05T04:41:59 Z |
Retro3014 |
Sails (IOI07_sails) |
C++17 |
|
982 ms |
9188 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){
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;
}
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].r].min);
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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(get(mid)==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(get(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, 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;
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);
}
}
for(int i=0; i<seg.size(); i++){
if(seg[i].s==seg[i].e){
ans+=((ll)seg[i].max)*(seg[i].max-1)/2;
}else{
if(seg[i].lazy>0){
seg[seg[i].l].max+=seg[i].lazy; seg[seg[i].l].min+=seg[i].lazy; seg[seg[i].l].lazy+=seg[i].lazy;
seg[seg[i].r].max+=seg[i].lazy; seg[seg[i].r].min+=seg[i].lazy; seg[seg[i].r].lazy+=seg[i].lazy;
seg[i].lazy=0;
}
}
}
printf("%lld\n", ans);
return 0;
}
Compilation message
sails.cpp: In function 'int main()':
sails.cpp:197:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<seg.size(); i++){
~^~~~~~~~~~~
sails.cpp:174:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
sails.cpp:178: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 |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
760 KB |
Output is correct |
| 2 |
Correct |
23 ms |
7792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
2348 KB |
Output is correct |
| 2 |
Correct |
123 ms |
924 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
2420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
374 ms |
4476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
836 ms |
9036 KB |
Output is correct |
| 2 |
Correct |
610 ms |
9100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
656 ms |
9060 KB |
Output is correct |
| 2 |
Correct |
295 ms |
9180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
982 ms |
9188 KB |
Output is correct |
| 2 |
Correct |
451 ms |
4840 KB |
Output is correct |
