QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#112019#6533. Traveling in Cells__stickWA 746ms31812kbC++203.3kb2023-06-09 14:57:172023-06-09 14:57:19

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-09 14:57:19]
  • 评测
  • 测评结果:WA
  • 用时:746ms
  • 内存:31812kb
  • [2023-06-09 14:57:17]
  • 提交

answer

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
template<typename T>
inline bool cmax(T&x,const T& y){return x<y?x=y,1:0;}
template<typename T>
inline bool cmin(T&x,const T& y){return y<x?x=y,1:0;}
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vii; 
typedef unsigned long long ull;
#define sz(x) (int(x.size()))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define em emplace
#define X first
#define Y second
const int mod=998244353;
inline void MOD(int&x){x-=mod,x+=x>>31&mod;}
inline void MOD(ll& x){x-=mod,x+=x>>63&mod;}
inline int add(int x,int y){MOD(x+=y);return x;}
inline int mul(int x,int y){return 1ll*x*y%mod;}
template<typename ... A>inline int mul(const int& x,const A&... p){return 1ll*x*mul(p...)%mod;}
inline ll ksm(ll a,ll p=mod-2){ll ans=1;for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;return ans;}
typedef long double LD;
const int MAXN=1e5+10;
int c[MAXN],a[MAXN];
int N;
struct BIT
{
    ll t[MAXN];
    inline void add(int x,int k){for(;x<=N;x+=x&-x)t[x]+=k;}
    inline ll ask(int x){ll ans=0;for(;x;x-=x&-x)ans+=t[x];return ans;}
    inline ll ask(int l,int r){return ask(r)-ask(l-1);}
}bt;
inline ll getid(ll x,ll y){return (x-1)*N+y;}
cc_hash_table<ll,int>t;
inline void add(int x,int y,int k)
{
    for(;y<=N;y+=y&-y)t[getid(x,y)]+=k;
}
inline int ask(vi& ve,int y)
{
    int ans=0;
    for(;y;y-=y&-y)
    {
        for(auto&x:ve)ans+=t[getid(x,y)];
    }
    return ans;
}
int M;
inline int findl(vi& ve,int x)
{
    int sum=ask(ve,x);
    if(sum==x)return 1;
    int tot=0,u=0;
    for(int i=M;i;i>>=1)
    {
        int nxt=u|i;
        int res=0;
        for(auto&p:ve)
        {
            auto ii=t.find(getid(p,nxt));
            if(ii!=t.end())res+=ii->second;
        }
        if(nxt<=x&&sum-(res+tot)!=x-nxt)u=nxt,tot+=res;
    }
    return u+2;
}
inline int findr(vi&ve,int x)
{
    auto b=ask(ve,x);
    int u=0,tot=0;
    for(int i=M;i;i>>=1)
    {
        int nxt=u|i;
        int res=0;
        for(auto&p:ve)
        {
            auto ii=t.find(getid(p,nxt));
            if(ii!=t.end())res+=ii->second;
        }
        if(nxt<x||(tot+res)-b==nxt-x)u=nxt,tot+=res;
    }
    return u;
}
inline void solve()
{
    t.clear();
    int n,m;cin>>n>>m;N=n;
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=1;i<=n;i++)bt.t[i]=0;
    for(int i=1;i<=n;i++)cin>>a[i],bt.add(i,a[i]),add(c[i],i,1);
    M=1;while(M<=n)M<<=1;
    while(m--)
    {
        int op,x,y;
        cin>>op;
        if(op==1)
        {
            cin>>x>>y;
            add(c[x],x,-1);
            add(c[x]=y,x,1);
        }
        else if(op==2)
        {
            cin>>x>>y;
            bt.add(x,-a[x]);
            bt.add(x,a[x]=y);
        }
        else
        {
            vi ve;cin>>x>>y;ve.resize(y);
            for(auto&p:ve)cin>>p;
          //  cerr<<findl(ve,x)<<' '<<findr(ve,x)<<'\n';
            cout<<bt.ask(findl(ve,x),findr(ve,x))<<'\n';
        }
    }
}
int main()
{
    
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cout<<fixed<<setprecision(10);
	int T;cin>>T;while(T--)solve();
	return 0;
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3464kb

input:

2
5 10
1 2 3 1 2
1 10 100 1000 10000
3 3 1 3
3 3 2 2 3
2 5 20000
2 3 200
3 3 2 1 3
3 3 3 1 2 3
1 3 4
2 1 100000
1 2 2
3 1 2 1 2
4 1
1 2 3 4
1000000 1000000 1000000 1000000
3 4 4 1 2 3 4

output:

100
110
1200
21211
100010
4000000

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 319ms
memory: 3428kb

input:

20000
15 15
1 1 3 3 2 3 3 3 3 3 2 3 2 3 3
634593973 158136379 707704004 998369647 831633445 263092797 937841412 451774682 552617416 483763379 50360475 794662797 74247465 537217773 901809831
3 6 4 1 3 5 10
3 5 7 1 2 3 4 5 9 10
3 4 3 3 8 9
2 13 608033129
3 15 2 3 5
1 9 3
3 8 4 1 3 7 10
2 6 727472865
3...

output:

2689089686
8377825475
1706073651
1439027604
2689089686
792730352
8904867081
8904867081
8270273108
831633445
692051585
2782432626
697783016
883944422
184057757
287523250
184057757
696388752
184057757
1675459344
2667693025
2614711258
4006992373
1767091974
5348541057
5348541057
390631780
2290216252
942...

result:

ok 200062 numbers

Test #3:

score: 0
Accepted
time: 376ms
memory: 3476kb

input:

2000
150 150
8 3 8 8 8 6 8 4 2 7 6 8 8 5 8 7 7 8 5 6 8 8 6 8 8 8 8 7 8 6 6 8 8 8 6 2 3 4 8 8 7 8 5 8 2 6 8 7 8 8 6 8 6 8 3 8 8 8 8 4 7 8 7 3 7 6 7 5 5 8 6 8 8 6 3 8 6 7 6 8 8 7 4 8 6 7 8 7 7 7 7 8 8 8 8 2 5 2 8 8 6 7 6 3 8 8 7 8 8 8 6 6 8 6 6 7 5 8 8 8 7 8 7 7 6 8 8 8 8 8 8 6 5 7 5 5 8 7 8 7 7 7 6 5...

output:

4449391171
3290849667
852793841
5178673994
995994209
11431868919
4327723427
5071541023
3032743466
962345334
2997656427
4534278452
3851900075
3611231417
5071541023
1477584218
1299005818
1299005818
2145605244
854143763
886347565
2081234124
2333808475
2455955801
4179722063
2328504333
1473735464
4107685...

result:

ok 199987 numbers

Test #4:

score: 0
Accepted
time: 596ms
memory: 14916kb

input:

10
30000 30000
3 4 2 4 4 4 4 3 4 3 4 3 4 3 4 4 2 4 4 4 4 4 3 3 3 4 3 4 3 4 3 3 4 2 4 3 3 3 3 4 3 4 4 4 4 2 3 3 4 2 3 4 4 4 4 1 4 4 4 4 4 4 4 4 3 3 3 4 4 4 4 4 2 3 4 4 4 4 3 4 4 3 3 3 4 4 3 4 4 2 3 4 4 4 4 3 2 4 3 4 3 2 4 4 3 4 2 2 4 4 4 4 2 4 3 2 4 4 3 4 4 4 2 4 4 3 2 3 2 3 3 3 4 2 4 3 4 1 4 3 4 4 4...

output:

6959437173
934970676
72461245502
8365928740
8384151048
984567228
12482909122
1904927816
15134139942
3759040688
92670874909
332468911
5936663371
3562978848
1300592004
10314009201
5581540905
131246926443
15087184135864
4077066271
1124704817
1520626740
4388174158
744377942
2770411457
6231852240
1508724...

result:

ok 200135 numbers

Test #5:

score: -100
Wrong Answer
time: 746ms
memory: 31812kb

input:

3
100000 100000
6 6 2 6 5 3 6 5 4 6 4 6 6 6 6 5 2 5 2 6 6 6 1 6 5 6 4 5 6 6 5 4 5 4 3 4 5 5 6 6 5 6 6 5 2 5 6 5 4 2 5 6 6 6 5 2 5 6 6 4 5 6 3 3 6 5 6 5 5 5 5 4 4 4 4 3 6 5 4 5 6 5 6 6 6 6 3 6 5 6 5 4 3 5 6 4 5 3 6 5 3 5 6 4 6 5 4 5 5 5 2 5 4 6 6 3 5 5 5 5 5 4 5 5 6 5 5 6 6 6 5 5 4 6 5 4 4 2 6 6 6 5 ...

output:

753014823
938372065
5655899645
168297301
14372254310
1066586326
3520855082
2591792266
2321844837
64378192092
250581310
1845085639
1402247975
198007248
2157074263
2743531397
3433471688
10332600792
1085086491
4845484125
4520682212879244457
4036199358
154762798
4520682212879244457
1221387905
1124079030...

result:

wrong answer 21st numbers differ - expected: '50019185900042', found: '4520682212879244457'