QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#393190 | #5449. 楼梯 | bachbeo2007 | 0 | 299ms | 60896kb | C++23 | 5.8kb | 2024-04-18 11:43:15 | 2024-04-18 11:43:18 |
Judging History
answer
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const long long inf=1e18;
const int mod=998244353;
const int maxn=300005;
const int B=650;
const int maxs=655;
const int maxm=200005;
const int maxq=1000005;
const int maxl=25;
const int maxa=1000000;
const int root=3;
const int base=101;
int m,S;
struct Query{
char op;
int a=0,b=0;
}qq[maxn];
vector<int> edge[maxn],com;
struct node{
int lt,rt,total=0;
int add=0,val=inf;
node(int a=0,int sz=0){
lt=rt=a;
total=(a>=1)*(sz-1);
}
friend node operator+(node a,node b){
node res;
res.lt=a.lt;
res.rt=b.rt;
res.total=a.total+b.total+a.rt-b.lt+(b.lt>=1);
return res;
}
};
node tree[4*maxn];
bool check(int id,int val){
if(val>0) return (tree[id].rt>0 || tree[id].lt==0);
else return (tree[id].rt+val>0 || tree[id].lt+val<=0);
}
void getnew(int l,int r,int id,int val){
tree[id]=node(val,r-l+1);
tree[id].val=val;
}
void getadd(int l,int r,int id,int val){
if(val<0 && tree[id].lt+val<=0){
getnew(l,r,id,0);
return;
}
if(val>0 && tree[id].lt==0){
getnew(l,r,id,val);
return;
}
tree[id].lt+=val;
tree[id].rt+=val;
if(tree[id].val!=inf) tree[id].val+=val;
else tree[id].add+=val;
}
void pushdown(int l,int r,int id){
int mid=(l+r)>>1;
if(tree[id].add!=0){
getadd(l,mid,id<<1,tree[id].add);
getadd(mid+1,r,id<<1|1,tree[id].add);
tree[id].add=0;
}
if(tree[id].val!=inf){
getnew(l,mid,id<<1,tree[id].val);
getnew(mid+1,r,id<<1|1,tree[id].val);
tree[id].val=inf;
}
}
void update(int l,int r,int id,int tl,int tr,int val){
if(tr<l || r<tl) return;
if(tl<=l && r<=tr && check(id,val)){
if(val>0){
if(tree[id].rt>0) getadd(l,r,id,val);
else getnew(l,r,id,val);
}
else{
if(tree[id].rt+val>0) getadd(l,r,id,val);
else getnew(l,r,id,0);
}
return;
}
pushdown(l,r,id);
int mid=(l+r)>>1;
update(l,mid,id<<1,tl,tr,val);update(mid+1,r,id<<1|1,tl,tr,val);
tree[id]=tree[id<<1]+tree[id<<1|1];
}
pii query(int l,int r,int id,int num){
if(l==r){
int sz=com[l]-com[l-1];
//cout << "query " << num << ' ' << sz << ' ' << tree[id].lt << '\n';
if(num<sz) return {com[l-1]+num-1,tree[id].lt};
num-=(sz-1);
return {com[l]-1,tree[id].lt-num+1};
}
pushdown(l,r,id);
int mid=(l+r)>>1;
int total=tree[id<<1].total+tree[id<<1].rt-tree[id<<1|1].lt+(tree[id<<1|1].lt>=1);
if(num>total) return query(mid+1,r,id<<1|1,num-total);
else return query(l,mid,id<<1,num);
}
void solve(){
cin >> m;
com.push_back(1);
for(int i=1;i<=m;i++){
cin >> qq[i].op >> qq[i].a;
if(qq[i].op=='+' || qq[i].op=='-'){
cin >> qq[i].b;
if(qq[i].op=='+') com.push_back(qq[i].a+1);
else com.push_back(qq[i].a);
}
}
sort(com.begin(),com.end());
com.erase(unique(com.begin(),com.end()),com.end());
S=(int)com.size()-1;
if(!S){
for(int i=1;i<=m;i++){
if(qq[i].op=='?') cout << -1 << ' ' << -1 << '\n';
}
return;
}
for(int i=1;i<=m;i++){
char op=qq[i].op;
int a=qq[i].a,b=qq[i].b;
if(op=='+'){
int pos=upper_bound(com.begin(),com.end(),a)-com.begin();
update(1,S,1,1,pos,b);
}
else if(op=='-'){
int pos=lower_bound(com.begin(),com.end(),a)-com.begin()+1;
update(1,S,1,pos,S,-b);
}
else if(op=='R'){
for(int j=i-a;j<i;j++) if(qq[j].op=='+'){
int pos=upper_bound(com.begin(),com.end(),qq[j].a)-com.begin();
update(1,S,1,1,pos,-qq[j].b);
}
}
else{
int l=1,r=(tree[1].total+tree[1].rt)/a;
if(r==0){
cout << -1 << ' ' << -1 << '\n';
}
else{
while(l<r){
int mid=(l+r)>>1;
pii p=query(1,S,1,mid*a);
pii q=query(1,S,1,mid*a+1);
if(p.fi==q.fi) r=mid;
else l=mid+1;
}
int X=query(1,S,1,(l-1)*a+1).fi;
int Y=query(1,S,1,l*a).se;
cout << X << ' ' << Y << '\n';
}
}
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int test=1;//cin >> test;
while(test--) solve();
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 12ms
memory: 57716kb
input:
1000 - 1 999995 ? 770771330 ? 688406105220012703 ? 466054413 ? 1466199 ? 940610359316496655 ? 310504014100463831 ? 765557590 ? 419614901 ? 830584303 ? 85199513 ? 768715778674812284 ? 742663363105169125 ? 859012516258231128 ? 168409807482711289 ? 842755243 ? 618667253264707663 ? 957265852 + 1 1 + 1 1...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 3 1 1 1 1 1 3 1 1 1 3 1 1 1 1 1 1 1 3 1 3 1 3 1 3 1 1 1 1 1 1 1 1 1 3 1 3 1 3 1 3 1 2 1 1 1 2 1 1 1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 ...
result:
wrong answer std found soln
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Wrong Answer
Test #111:
score: 10
Accepted
time: 48ms
memory: 57544kb
input:
300000 ? 308230551 ? 154394919 ? 77796824 ? 523232316 ? 601650936815206607 ? 986805724 ? 283169431815882827 ? 781223930 ? 785380179984309713 ? 36818911074958611 ? 452850684 ? 392810692 ? 812929344 ? 9753139 ? 236758865441063408 ? 448106017 ? 382652997142237763 ? 667762111 ? 201388730 ? 433119061 ? 6...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok ok
Test #112:
score: 0
Accepted
time: 43ms
memory: 59308kb
input:
300000 ? 694621109955041627 ? 142117945123014130 ? 271105710887553798 ? 588870805 ? 596999104759770886 ? 559345155 ? 913509137 ? 863050204268429730 ? 121648910055156360 ? 27539423 ? 237739281 ? 102014055246481880 ? 918066897 ? 150630127417587162 ? 675850416 ? 465834639 ? 242358214 ? 914838785 ? 3574...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok ok
Test #113:
score: -10
Wrong Answer
time: 299ms
memory: 60896kb
input:
300000 - 594041 389378 + 771465 5 + 12646 60 + 148838 36 + 30991 56 + 5527 60 + 488 60 + 17980 59 + 3243 60 + 846785 5 + 736073 5 + 206626 6 + 258271 6 + 8314 60 + 10126 60 + 574513 5 + 868009 5 + 22322 59 + 6150 60 + 448626 6 + 330651 6 + 308596 6 + 901966 4 + 10974 60 + 6572 60 + 25046 59 + 7370 6...
output:
16331 967297 -1 -1 15999 968857 16331 972816 1 1953994 16344 973476 16341 973296 14736 943604 -1 -1 1 1953972 1 1944470 1 1906373 9684 792086 9684 792086 16344 973476 16331 967297 16341 973296 1 1951924 1 1953994 1 1953990 -1 -1 16344 973476 14736 943604 16331 967297 16341 973296 16344 973476 15999 ...
result:
wrong answer query 48439: expected 7015 but got 7121
Subtask #7:
score: 0
Skipped
Dependency #1:
0%