QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#786 | #530481 | #8035. Call Me Call Me | hhy0613 | hhy0613 | Success! | 2024-08-24 17:49:02 | 2024-08-24 17:49:06 |
詳細信息
Extra Test:
Wrong Answer
time: 12ms
memory: 87628kb
input:
2 1 1 0 1 1 1
output:
1
result:
wrong answer 1st numbers differ - expected: '2', found: '1'
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#530481 | #8035. Call Me Call Me | hhy0613 | WA | 5575ms | 150064kb | C++14 | 4.7kb | 2024-08-24 16:22:55 | 2024-08-24 18:00:13 |
answer
#include<bits/stdc++.h>
using namespace std;
const int N=400005,INF=0x3f3f3f3f;
int l[N],r[N],c[N],nodeL[N],nodeR[N],n;
bool xing[N];
vector<int> vec[N<<2],qe;
bool vis[N];
struct AAA{
int val,pos;
bool operator<(const AAA& aa)const{return (val<aa.val || (val==aa.val && pos<aa.pos));}
};
vector<AAA> vev[N<<2];
namespace seg{
struct node{
node *left,*right;
int mn,add;
}pool[N*40];
int cnt;
node* New(int x){
pool[cnt]=node{nullptr,nullptr,x,0};
return pool+(cnt++);
}
void sol(node* p){p->mn=min(p->left->mn,p->right->mn);}
void add_add(node* p,int x){
if(p==nullptr) return;
p->mn+=x;
p->add+=x;
}
void push_down(node* p){
if(p==nullptr || p->add==0) return;
add_add(p->left,p->add);
add_add(p->right,p->add);
p->add=0;
}
node* build(const vector<int>& vec,int l,int r){
if(l==r) return nullptr;
if(l+1==r) return New(vec[l]);
int mid=l+(r-l)/2;
node* p=New(0);
p->left=build(vec,l,mid);
p->right=build(vec,mid,r);
sol(p);
return p;
}
void update(node* p,int l,int r,int pos,int x){
if(l+1==r){
p->mn=x;
return;
}
push_down(p);
int mid=l+(r-l)/2;
if(pos<mid) update(p->left,l,mid,pos,x);
else update(p->right,mid,r,pos,x);
sol(p);
}
int query(node* p,int l,int r,int pos){
if(l+1==r) return p->mn;
push_down(p);
int mid=l+(r-l)/2;
if(pos<mid) return query(p->left,l,mid,pos);
return query(p->right,mid,r,pos);
}
void add(node* p,int L,int R,int l,int r,int x){
if(p==nullptr || l>=r) return;
if(l<=L && R<=r){
add_add(p,x);
return;
}
push_down(p);
int mid=L+(R-L)/2;
if(l<mid) add(p->left,L,mid,l,r,x);
if(r>mid) add(p->right,mid,R,l,r,x);
sol(p);
}
void find0(node* p,int l,int r,vector<int>& vec){
if(p==nullptr || p->mn>0) return;
if(l+1==r){
vec.push_back(l);
return;
}
push_down(p);
int mid=l+(r-l)/2;
find0(p->left,l,mid,vec);
find0(p->right,mid,r,vec);
}
}
seg::node* root[N<<2];
void solve(int p){
if(root[p]==nullptr) return;
vector<int> vec;
seg::find0(root[p],0,(int)vev[p].size(),vec);
for(int ii:vec){
const int pos=vev[p][ii].pos;
if(vis[pos]) continue;
vis[pos]=true;
const int i=nodeL[pos],j=nodeR[pos];
const int v1=seg::query(root[p],0,(int)vev[p].size(),i),v2=seg::query(root[p],0,(int)vev[p].size(),j);
assert(v1>=0 && v2>=0 && (v1==0 || v2==0));
const int now=(v1+v2-(c[pos]&1));
c[pos]=now;
if(now==0){
qe.push_back(pos);
seg::update(root[p],0,(int)vev[p].size(),i,INF);
seg::update(root[p],0,(int)vev[p].size(),j,INF);
}else{
seg::update(root[p],0,(int)vev[p].size(),i,(now+1)/2);
seg::update(root[p],0,(int)vev[p].size(),j,(now+1)/2);
}
}
for(int i:vec) vis[vev[p][i].pos]=false;
}
void build(int p,int L,int R){
vev[p].clear();
for(int i:vec[p]){
vev[p].push_back(AAA{l[i],i});
vev[p].push_back(AAA{r[i],i});
}
sort(vev[p].begin(),vev[p].end());
for(int i=0;i<(int)vev[p].size();++i){
if(l[vev[p][i].pos]==vev[p][i].val) nodeL[vev[p][i].pos]=i;
else nodeR[vev[p][i].pos]=i;
}
vector<int> data;
for(int i=0;i<(int)vev[p].size();++i){
if(L+1==R) data.push_back(c[vev[p][i].pos]);
else data.push_back((c[vev[p][i].pos]+1)/2);
}
root[p]=seg::build(data,0,(int)data.size());
solve(p);
if(L+1==R) return;
int mid=L+(R-L)/2;
build(p*2+1,L,mid);
build(p*2+2,mid,R);
}
void update(int x){
int p=0,L=0,R=n;
while(true){
int mid=L+(R-L)/2;
const int pos=int(upper_bound(vev[p].begin(),vev[p].end(),AAA{x,INF})-vev[p].begin());
if(L+1==R){
seg::add(root[p],0,(int)vev[p].size(),int(lower_bound(vev[p].begin(),vev[p].end(),AAA{x,-INF})-vev[p].begin()),pos,-1);
return;
}
if(x<mid){
seg::add(root[p],0,(int)vev[p].size(),0,pos,-1);
solve(p);
}else{
seg::add(root[p],0,(int)vev[p].size(),pos,(int)vev[p].size(),-1);
solve(p);
}
if(x<mid){
p=2*p+1;
R=mid;
}else{
p=2*p+2;
L=mid;
}
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int T=1;
while(T--){
cin >> n;
for(int i=0;i<n;++i){
cin >> l[i] >> r[i] >> c[i];
--l[i];
}
seg::cnt=0;
for(int i=0;i<4*n;++i) vec[i].clear();
for(int i=0;i<n;++i){
int p=0,L=0,R=n;
while(true){
int mid=L+(R-L)/2;
if(l[i]<=mid && mid<r[i]){
vec[p].push_back(i);
break;
}
if(r[i]<=mid){
p=2*p+1;
R=mid;
}else{
p=2*p+2;
L=mid;
}
}
}
qe.clear();
int start=0;
build(0,0,n);
for(int i=0;i<n;++i) xing[i]=false;
while(start<(int)qe.size()){
const int u=qe[start++];
update(u);
xing[u]=true;
}
int ans=0;
for(int i=0;i<n;++i) ans+=xing[i];
cout << ans << '\n';
}
return 0;
}