oj.uz

답안 #837048

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
837048 2023-08-24T20:27:32 Z NemanjaSo2005 Matching (CEOI11_mat) C++17
100 / 100
 1494 ms 65536 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+5;
int MOD=1e9+9,b=1e6+3;
int N,K,M,H,H2,kol[maxn],fwt[maxn],niz[maxn],stepen[maxn];
pair<int,int> sniz[maxn];
vector<int> R;
void fadd(int gde,int kol){
   for(int i=gde;i<=M;i+=i&-i)
      fwt[i]+=kol;
   return;
}
int fget(int gde){
   int ret=0;
   for(int i=gde;i>=1;i-=i&-i)
      ret+=fwt[i];
   return ret;
}
struct cvor{
   int rez,mlt,cur;
}c1,c2,st[2100000];
cvor opr(cvor a,cvor b){
   a.rez=(a.rez+b.rez+(ll)a.cur*b.mlt)%MOD;
   a.cur+=b.cur;
   a.mlt+=b.mlt;
   if(a.mlt>=MOD)
      a.mlt-=MOD;
   return a;
}
void prop(int gde){
   st[gde*2]=opr(st[gde*2],st[gde]);
   st[gde*2+1]=opr(st[gde*2+1],st[gde]);
   st[gde].rez=0;
   st[gde].mlt=0;
   st[gde].cur=0;
}
void update(int lg,int dg,cvor sta,int gde=1,int lc=1,int dc=K){
   if(lg==lc and dg==dc){
      st[gde]=opr(st[gde],sta);
      return;
   }
   prop(gde);
   int sred=(lc+dc)/2;
   if(dg<=sred)
      return update(lg,dg,sta,gde*2,lc,sred);
   if(lg>sred)
      return update(lg,dg,sta,gde*2+1,sred+1,dc);
   update(lg,sred,sta,gde*2,lc,sred);
   update(sred+1,dg,sta,gde*2+1,sred+1,dc);
   return;
}
void add(int l,int r){
   if(r<l)
      return;
   cvor x;
   x.mlt=0;
   x.rez=0;
   x.cur=1;
   update(l,r,x);
}
void multi(int l,int r,int kol){
   if(r<l)
      return;
   cvor x;
   x.rez=0;
   x.cur=0;
   x.mlt=kol;
   update(l,r,x);
}
int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   stepen[0]=1;
   N=1e6;
   for(int i=1;i<=N;i++)
      stepen[i]=stepen[i-1]*(ll)b%MOD;
   cin>>N>>M;
   K=1;
   while(K<M)
      K<<=1;
   int a;
   for(int i=1;i<=N;i++){
      cin>>a;
      niz[a]=i;
   }
   for(int i=1;i<=N;i++){
      fadd(niz[i],1);
      H=(H+((ll)i-fget(niz[i]))*stepen[i])%MOD;
   }
   for(int i=1;i<=M;i++)
      cin>>niz[i];
   for(int i=1;i<=M;i++){
      sniz[i].first=niz[i];
      sniz[i].second=i;
   }
   sort(sniz+1,sniz+1+M);
   for(int i=1;i<=M;i++)
      niz[sniz[i].second]=i;
   memset(fwt,0,sizeof(fwt));
   for(int i=1;i<=M;i++){
      fadd(niz[i],1);
      kol[i]=i-fget(niz[i]);
   }
   for(int i=M;i>=1;i--){
      int p=sniz[i].second;
      add(p,M);
      multi(max(1,p-N),p-1,stepen[p]);
   }
   for(int i=1;i<K;i++)
      prop(i);
   for(int i=1;i<=N;i++)
      H2=(H2+(ll)kol[i]*stepen[i])%MOD;
   if(H==H2)
      R.push_back(1);
   for(int i=2;i+N-1<=M;i++){
      H=(H*(ll)b)%MOD;
      H2-=kol[i-1]*(ll)stepen[i-1]%MOD;
      if(H2<0)
         H2+=MOD;
      H2+=kol[i+N-1]*(ll)stepen[i+N-1]%MOD;
      if(H2>=MOD)
         H2-=MOD;
      int tmp=H2-st[K+i-2].rez;
      if(tmp<0)
         tmp+=MOD;
      if(tmp==H)
         R.push_back(i);
   }
   cout<<R.size()<<"\n";
   for(int i=0;i<R.size();i++)
      cout<<R[i]<<" ";
   cout<<"\n";
   return 0;
}

Compilation message

mat.cpp: In function 'int main()':
mat.cpp:131:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |    for(int i=0;i<R.size();i++)
      |                ~^~~~~~~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 8148 KB Output is correct
2 Correct 10 ms 8148 KB Output is correct
3 Correct 10 ms 8148 KB Output is correct
4 Correct 11 ms 8168 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 8148 KB Output is correct
2 Correct 11 ms 8148 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 9224 KB Output is correct
2 Correct 26 ms 9172 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 9164 KB Output is correct
2 Correct 30 ms 9228 KB Output is correct
3 Correct 12 ms 8276 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 17040 KB Output is correct
2 Correct 195 ms 17228 KB Output is correct
3 Correct 231 ms 17356 KB Output is correct
4 Correct 228 ms 17356 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 216 ms 17740 KB Output is correct
2 Correct 229 ms 17444 KB Output is correct
3 Correct 211 ms 17704 KB Output is correct
4 Correct 158 ms 19580 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 211 ms 17808 KB Output is correct
2 Correct 200 ms 17356 KB Output is correct
3 Correct 235 ms 17396 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1251 ms 48972 KB Output is correct
2 Correct 1291 ms 64716 KB Output is correct
3 Correct 1098 ms 52440 KB Output is correct

Subtask #9
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1069 ms 47668 KB Output is correct
2 Correct 1282 ms 55072 KB Output is correct
3 Correct 1308 ms 61488 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1147 ms 49360 KB Output is correct
2 Correct 868 ms 65536 KB Output is correct
3 Correct 1494 ms 57772 KB Output is correct
4 Correct 926 ms 62840 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1117 ms 49600 KB Output is correct
2 Correct 1349 ms 58628 KB Output is correct
3 Correct 496 ms 32448 KB Output is correct
4 Correct 1026 ms 63272 KB Output is correct