ACM-ICPC 2018 徐州赛区网络预赛 - G Trace - 思维
ACM-ICPC 2018 徐州赛区网络预赛 - G Trace - 思维
There’s a beach in the first quadrant. And from time to time, there are sea waves. A wave ( xxx , yyy ) means the wave is a rectangle whose vertexes are ( 000 , 000 ), ( xxx , 000 ), ( 000 , yyy ), ( xxx , yyy ). Every time the wave will wash out the trace of former wave in its range and remain its own trace of ( xxx , 000 ) -> ( xxx , yyy ) and ( 000 , yyy ) -> ( xxx , yyy ). Now the toad on the coast wants to know the total length of trace on the coast after n waves. It’s guaranteed that a wave will not cover the other completely.
Input
The first line is the number of waves n(n≤50000)n(n \le 50000)n(n≤50000).
The next nnn lines,each contains two numbers xxx yyy , 10000000y≤10000000 ),the iii-th line means the iii-th second there comes a wave of ( xxx , yyy ), it’s guaranteed that when 1≤i1 \le i1≤i , j≤nj \le nj≤n ,xi≤xjx_i \le x_jxi≤xj and yi≤yjy_i \le y_jyi≤yj don’t set up at the same time.
Output
An Integer stands for the answer.
Hint:
As for the sample input, the answer is 3+3+1+1+1+1=103+3+1+1+1+1=103+3+1+1+1+1=10
样例输入
3
1 4
4 1
3 3
样例输出
10
题目来源
ACM-ICPC 2018 徐州赛区网络预赛
分析:
这是道让人想不到的思维题,实在解释不了其道理看博客吧传送门你们都什么脑子啊怎么想到的。。。太可怕了。。
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 50005;
int n;
ll X[N],Y[N];
ll solve(ll a[]){
set<int> used;
set<int>::iterator it;
ll ans = 0;
for(int i = n; i >= 1; i--){
it = used.lower_bound(a[i]);
if(it == used.begin()) ans += a[i];
else{
it--;
ans += a[i] - *it;
}
used.insert(a[i]);
}
return ans;
}
int main(){
scanf("%d",&n);
for(int i = 1; i <= n; i++){
scanf("%lld%lld",&X[i],&Y[i]);
}
ll ans = solve(X) + solve(Y);
printf("%lld\n",ans);
return 0;
}
推荐阅读
-
ACM-ICPC 2018 徐州赛区网络预赛 H - Ryuji doesn't want to study
-
ACM-ICPC 2018 徐州赛区网络预赛 H. Ryuji doesn't want to study(线段树区间求和)
-
ACM-ICPC 2018 徐州赛区网络预赛 H. Ryuji doesn't want to study—— 树状数组
-
ACM-ICPC 2018 徐州赛区网络预赛 H Ryuji doesn't want to study(线段树 两种做法)
-
【ACM-ICPC 2018 徐州赛区网络预赛】H题 Features Track ---- 树状数组
-
ACM-ICPC 2018 徐州赛区网络预赛 G. Trace (线段树维护)
-
计蒜客 Trace(2018 ICPC亚洲区域赛网络赛 徐州 G)(线段树)
-
ACM-ICPC 2018 徐州赛区网络预赛 Trace
-
Trace-----ACM-ICPC 2018 徐州赛区网络预赛
-
ACM-ICPC 2018 沈阳赛区网络预赛 F题 Fantastic Graph