2017 ACM-ICPC 亚洲区（南宁赛区）网络赛 B. Train Seats Reservation 和 F. Overlapping Rectangles

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include<list>
#include <bitset>
#include <climits>
#include <algorithm>
#define gcd(a,b) __gcd(a,b)
#define FIN	freopen("input.txt","r",stdin)
#define FOUT
freopen("output.txt","w",stdout)
typedef long long LL;
const LL mod=1e9+7;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
using namespace std;
struct node{
int s,t;
int k;
int flag;
}a[1005];
int cmp(node x,node y){
return x.s<y.s;
}
int main (){
int t;
while (scanf ("%d",&t)&&t){
for (int i=0;i<t;i++) scanf ("%d%d%d",&a[i].s,&a[i].t,&a[i].k),a[i].flag=0;
sort(a,a+t,cmp);
int sum=a[0].k;
int maxn=0;
for (int i=1;i<t;i++){
sum+=a[i].k;
for (int j=i-1;j>=0;j--){
if (a[i].s>=a[j].t&&a[j].flag!=-1) a[j].flag=-1,sum-=a[j].k;
}
if (maxn<sum) maxn=sum;
}
printf ("%dn",maxn);
}
printf ("*n");
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include<list>
#include <bitset>
#include <climits>
#include <algorithm>
#define gcd(a,b) __gcd(a,b)
typedef long long LL;
const LL mod=1e9+7;
const int INF=0x3f3f3f3f;
const int MAX=1e6+5;
const double PI=acos(-1.0);
using namespace std;
struct node{//
存储矩形边的信息
LL x1,x2,h;
int flag;//
出边还是入边
}a[MAX];
struct Tree{
int l,r;
LL len;
int s;
}T[MAX];
LL ls[MAX];//
离散化
bool cmp(node x,node y){
return x.h<y.h;
}
void pushUP(int rt){//
标记上推
if(T[rt].s) T[rt].len=ls[T[rt].r+1]-ls[T[rt].l];
else if (T[rt].l==T[rt].r) T[rt].len=0;
else T[rt].len=T[rt*2].len+T[rt*2+1].len;
}
void build(int rt,int l,int r){//
建树
T[rt].s=0;T[rt].len=0;
T[rt].l=l;T[rt].r=r;
if (l==r) return ;
int mid=(l+r)/2;
build(rt*2,l,mid);
build(rt*2+1,mid+1,r);
}
void update(int rt,int l,int r,int e){//
修改区间
if (T[rt].l>=l&&T[rt].r<=r){
T[rt].s+=e;
pushUP(rt);
return ;
}
int mid=(T[rt].l+T[rt].r)/2;
if (r<=mid) update(rt*2,l,r,e);
else if (l>mid) update(rt*2+1,l,r,e);
else {
update(rt*2,l,mid,e);
update(rt*2+1,mid+1,r,e);
}
pushUP(rt);
}
int main (){
int n;
while (scanf ("%d",&n)){
if(!n){
printf ("*n");
break;
}
int len=0;
for (int i=0;i<n;i++){
LL x1,y1,x2,y2;
scanf ("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
a[len].x1=x1;a[len].x2=x2;a[len].h=y1;
a[len].flag=1;ls[len]=x1;len++;
a[len].x1=x1;a[len].x2=x2;a[len].h=y2;
a[len].flag=-1;ls[len]=x2;len++;
}
sort(ls,ls+len);
sort(a,a+len,cmp);
len=unique(ls,ls+len)-ls;
build(1,0,len-1);
LL ans=0;
for (int i=0;i<2*n;i++){
int l=lower_bound(ls,ls+len,a[i].x1)-ls;
int r=lower_bound(ls,ls+len,a[i].x2)-ls-1;
update(1,l,r,a[i].flag);
ans+=T[1].len*(a[i+1].h-a[i].h);
}
printf("%lldn",ans);
}
}