当前位置:网站首页>Codeforces 12D ball tree array simulation 3 sorting elements
Codeforces 12D ball tree array simulation 3 sorting elements
2022-07-05 21:43:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack
Topic links : Click to open the link
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<set>
#include<vector>
#include<map>
#include<math.h>
#include<queue>
#include<string>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define N 500005
#define ll int
ll n;
ll c[N], maxn;
inline ll lowbit(ll x){return x&(-x);}
void change(ll pos, ll val){
while(pos)c[pos]=max(c[pos],val), pos-=lowbit(pos);
}
ll maxx(ll pos){
ll ans = -1;
while(pos<=maxn)ans = max(ans,c[pos]),pos+=lowbit(pos);
return ans;
}
struct node{
ll b[3],num;
}w[N];
bool cmp0(node x, node y){return x.b[0]<y.b[0];}
bool cmp1(node x, node y){return x.b[1]>y.b[1];}
int main(){
ll i,j;
while(cin>>n) {
for(i=0;i<n;i++)scanf("%d",&w[i].b[0]);
for(i=0;i<n;i++)scanf("%d",&w[i].b[1]);
for(i=0;i<n;i++)scanf("%d",&w[i].b[2]);
sort(w, w+n, cmp0);
ll rank = 1;
w[0].num = 1;
for(i=1;i<n;i++) {
if(w[i].b[0]==w[i-1].b[0])w[i].num = rank;
else w[i].num = ++rank;
}
sort(w,w+n,cmp1);
for(i=1;i<=rank;i++)c[i]=-1;
maxn = rank;
i = 0;
ll ans = 0;
while(i<n) {
for(j = i; j < n && w[i].b[1] == w[j].b[1]; j++)
if(maxx(w[j].num+1)>w[j].b[2])
ans++;
for(j = i; j < n && w[i].b[1] == w[j].b[1]; j++)
change(w[j].num, w[j].b[2]);
i = j;
}
cout<<ans<<endl;
}
return 0;
}
Copyright notice : This article is an original blog article , Blog , Without consent , Shall not be reproduced .
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/117583.html Link to the original text :https://javaforall.cn
边栏推荐
- 华为云ModelArts文本分类–外卖评论
- Selenium finds the contents of B or P Tags
- EBS Oracle 11g 克隆步骤(单节点)
- Three components of openpyxl
- leetcode:1755. Sum of subsequences closest to the target value
- 2.2.5 basic sentences of R language drawing
- 办公遇到的问题--
- Postgres establish connection and delete records
- EasyExcel的讀寫操作
- Sorting out the problems encountered in MySQL built by pycharm connecting virtual machines
猜你喜欢
Cold violence -- another perspective of objective function setting
Deployment of Jenkins under win7
Zhang Lijun: penetrating uncertainty depends on four "invariants"
Defect detection - Halcon surface scratch detection
MMAP
xlrd常见操作
Huawei game multimedia service calls the method of shielding the voice of the specified player, and the error code 3010 is returned
Clickhouse copy paste multi line SQL statement error
Xlrd common operations
QML reported an error expected token ";", expected a qualified name ID
随机推荐
ESP32
阿里云有奖体验:用PolarDB-X搭建一个高可用系统
总结出现2xx、3xx、4xx、5xx状态码的原因
oracle 控制文件的多路复用
Feng Tang's "spring breeze is not as good as you" digital collection, logged into xirang on July 8!
2022-07-03-cka- latest feedback from fans
What are the requirements of UL 2043 test for drive housing in the United States?
Summarize the reasons for 2XX, 3xx, 4xx, 5xx status codes
Efficiency difference between row first and column first traversal of mat data types in opencv
2.2.3 output of documents
Yolov5 training custom data set (pycharm ultra detailed version)
Oracle HugePages没有被使用导致服务器很卡的解决方法
基于 Ingress Controller 在集群外访问 Zadig 自测环境(最佳实践)
Four components of logger
123456
matlab绘制hsv色轮图
854. 相似度为 K 的字符串 BFS
[daily training] 729 My schedule I
Three components of openpyxl
postgres 建立连接并删除记录