QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#393190#5449. 楼梯bachbeo20070 299ms60896kbC++235.8kb2024-04-18 11:43:152024-04-18 11:43:18

Judging History

你现在查看的是最新测评结果

  • [2024-04-18 11:43:18]
  • 评测
  • 测评结果:0
  • 用时:299ms
  • 内存:60896kb
  • [2024-04-18 11:43:15]
  • 提交

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();
}

Details

Tip: Click on the bar to expand more detailed information

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%