QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #697394 | #4088. 총 쏘기 | Matutino | Compile Error | / | / | C++17 | 3.3kb | 2024-11-01 13:50:08 | 2024-11-01 13:50:09 |
Judging History
answer
#include<bits/stdc++.h>
#define reg register
inline bool cmax(reg int &x,reg int y){return x<y?x=y,1:0;}
const int N=5e5+10;
int n,a[N],b[N],rk[N],g[N];
std::vector<int> vc[N];
struct BIT{
int c[N];
inline void mdf(reg int x,reg int k){for (;x<=n;x+=x&-x) cmax(c[x],k);}
inline int qry(reg int x){reg int res=0;for (;x;x-=x&-x) cmax(res,c[x]); return res;}
}T;
namespace DS{
int rt[N<<2],ls[N<<7],rs[N<<7],mx[N<<7],idx;
void modify(reg int &o,reg int l,reg int r,reg int x,reg int k){
if (!o) o=++idx; cmax(mx[o],k); if (l==r) return; reg int mid=l+r>>1;
x<=mid?modify(ls[o],l,mid,x,k):modify(rs[o],mid+1,r,x,k);
}
void Modify(reg int o,reg int l,reg int r,reg int x,reg int y,reg int k){
modify(rt[o],1,n,y,k); if (l==r) return; reg int mid=l+r>>1;
x<=mid?Modify(o<<1,l,mid,x,y,k):Modify(o<<1|1,mid+1,r,x,y,k);
}
int query(reg int o,reg int l,reg int r,reg int L,reg int R){
if (!o) return 0; if (L<=l&&r<=R) return mx[o]; reg int mid=l+r>>1,res=0;
if (L<=mid) cmax(res,query(ls[o],l,mid,L,R)); if (R>mid) cmax(res,query(rs[o],mid+1,r,L,R)); return res;
}
int Query(reg int o,reg int l,reg int r,reg int L,reg int R,reg int p,reg int q){
if (L<=l&&r<=R) return query(rt[o],1,n,p,qsss); reg int mid=l+r>>1,res=0;
if (L<=mid) cmax(res,Query(o<<1,l,mid,L,R,p,q)); if (R>mid) cmax(res,Query(o<<1|1,mid+1,r,L,R,p,q)); return res;
}
}
struct Segment{
std::pair<int,int> mx[N<<2];
void modify(reg int o,reg int l,reg int r,reg int x,reg std::pair<int,int> k){
if (l==r) return mx[o]=k,void(); reg int mid=l+r>>1;
x<=mid?modify(o<<1,l,mid,x,k):modify(o<<1|1,mid+1,r,x,k); mx[o]=std::max(mx[o<<1],mx[o<<1|1]);
}
std::pair<int,int> query(reg int o,reg int l,reg int r,reg int L,reg int R){
if (L<=l&&r<=R) return mx[o]; reg int mid=l+r>>1; reg std::pair<int,int> res={0,0};
if (L<=mid) res=std::max(res,query(o<<1,l,mid,L,R)); if (R>mid) res=std::max(res,query(o<<1|1,mid+1,r,L,R)); return res;
}
}T2;
std::vector<std::pair<int,int>> min_shooting_buildings(std::vector<int> H){
n=H.size(); for (reg int i=0;i<n;i++) g[a[i+1]=H[i]]=i+1;
for (reg int i=n;i;i--) vc[b[i]=T.qry(a[i])+1].push_back(i),T.mdf(a[i],b[i]);
for (reg int i=1,cnt=0;i<=n;i++){
std::sort(vc[i].begin(),vc[i].end(),[](reg int x,reg int y){
if (x<y){if (a[x]>a[y]) return false; return DS::Query(1,1,n,x,y-1,1,a[x])<DS::Query(1,1,n,y,n,a[x]+1,a[y]);}
else{if (a[x]<a[y]) return true; return DS::Query(1,1,n,x,n,a[y]+1,a[x])<DS::Query(1,1,n,y,x-1,1,a[y]);}
});
for (auto it:vc[i]) DS::Modify(1,1,n,it,a[it],rk[it]=++cnt);
}
std::priority_queue<std::pair<int,int>> pq;
std::vector<std::pair<int,int>> ans;
std::set<int> s;
for (reg int i=1,pre=0;i<=n;i++){
T2.modify(1,1,n,i,{a[i],i});
if (pre<a[i]) pq.push({rk[i],i}),s.insert(a[i]),pre=a[i];
}
auto del=[&](reg int x)->void {
s.erase(a[x]),T2.modify(1,1,n,x,{0,0});
auto it=s.upper_bound(a[x]);
reg int r=it==s.end()?n:g[*it]-1,mn=0;
if (it!=s.begin()) mn=*--it;
while (x<r){
auto [v,p]=T2.query(1,1,n,x,r); if (v<=mn) break;
s.insert(v),pq.push({rk[p],p}),r=p-1;
}
};
while (!pq.empty()){
auto [px,x]=pq.top(); pq.pop();
// std::cerr<<x<<"\n";
if (!pq.empty()){
auto [py,y]=pq.top(); pq.pop();
ans.push_back({a[x],a[y]}),del(y);
}else ans.push_back({a[x],a[x]}); del(x);
}
return ans;
}
Details
answer.code:3:27: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
3 | inline bool cmax(reg int &x,reg int y){return x<y?x=y,1:0;}
| ^
answer.code:3:37: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
3 | inline bool cmax(reg int &x,reg int y){return x<y?x=y,1:0;}
| ^
answer.code:9:33: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
9 | inline void mdf(reg int x,reg int k){for (;x<=n;x+=x&-x) cmax(c[x],k);}
| ^
answer.code:9:43: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
9 | inline void mdf(reg int x,reg int k){for (;x<=n;x+=x&-x) cmax(c[x],k);}
| ^
answer.code:10:32: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
10 | inline int qry(reg int x){reg int res=0;for (;x;x-=x&-x) cmax(res,c[x]); return res;}
| ^
answer.code: In member function ‘int BIT::qry(int)’:
answer.code:10:43: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
10 | inline int qry(reg int x){reg int res=0;for (;x;x-=x&-x) cmax(res,c[x]); return res;}
| ^~~
answer.code: At global scope:
answer.code:14:30: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
14 | void modify(reg int &o,reg int l,reg int r,reg int x,reg int k){
| ^
answer.code:14:40: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
14 | void modify(reg int &o,reg int l,reg int r,reg int x,reg int k){
| ^
answer.code:14:50: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
14 | void modify(reg int &o,reg int l,reg int r,reg int x,reg int k){
| ^
answer.code:14:60: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
14 | void modify(reg int &o,reg int l,reg int r,reg int x,reg int k){
| ^
answer.code:14:70: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
14 | void modify(reg int &o,reg int l,reg int r,reg int x,reg int k){
| ^
answer.code: In function ‘void DS::modify(int&, int, int, int, int)’:
answer.code:15:75: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
15 | if (!o) o=++idx; cmax(mx[o],k); if (l==r) return; reg int mid=l+r>>1;
| ^~~
answer.code: At global scope:
answer.code:18:29: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
18 | void Modify(reg int o,reg int l,reg int r,reg int x,reg int y,reg int k){
| ^
answer.code:18:39: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
18 | void Modify(reg int o,reg int l,reg int r,reg int x,reg int y,reg int k){
| ^
answer.code:18:49: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
18 | void Modify(reg int o,reg int l,reg int r,reg int x,reg int y,reg int k){
| ^
answer.code:18:59: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
18 | void Modify(reg int o,reg int l,reg int r,reg int x,reg int y,reg int k){
| ^
answer.code:18:69: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
18 | void Modify(reg int o,reg int l,reg int r,reg int x,reg int y,reg int k){
| ^
answer.code:18:79: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
18 | void Modify(reg int o,reg int l,reg int r,reg int x,reg int y,reg int k){
| ^
answer.code: In function ‘void DS::Modify(int, int, int, int, int, int)’:
answer.code:19:66: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
19 | modify(rt[o],1,n,y,k); if (l==r) return; reg int mid=l+r>>1;
| ^~~
answer.code: At global scope:
answer.code:22:27: warning: ISO C++17 does not allo...