oj.uz

Submission #836687

# Submission time Handle Problem Language Result Execution time Memory
836687 2023-08-24T14:02:02 Z NemanjaSo2005 Matching (CEOI11_mat) C++17
0 / 100
 211 ms 46424 KB 
/// MLE TEST
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int N,K,M,patern[1000005],niz[1000005],oduz[1000005];
int MOD=1000000009,b=1000037,stepen[1000005];
//vector<int> on[1000005],off[1000005];
struct slog{
   int sv,poz;
} sniz[1000005];
bool posv(slog a,slog b){
   return a.sv<b.sv;
}
struct cvor{
   int cnt,mlt,rez;
   bool on;
}st[4200000];
cvor opr(cvor a,cvor b){
   if(a.on==false)
      return b;
   if(b.on==false)
      return a;
   a.rez=(a.rez+b.rez+(ll)a.cnt*b.mlt)%MOD;
   a.mlt+=b.mlt;
   if(a.mlt>=MOD)
      a.mlt-=MOD;
   a.cnt+=b.cnt;
   return a;
}
void update(int gde,bool akt){
   st[gde].on=akt;
   gde/=2;
   while(gde){
      st[gde]=opr(st[gde*2],st[gde*2+1]);
      gde/=2;
   }
}
int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cin>>N>>M;
   stepen[0]=1;
   for(int i=1;i<=M;i++)
      stepen[i]=(stepen[i-1]*(ll)b)%MOD;
   K=1;
   while(K<2*M)
      K<<=1;
   for(int i=1;i<=N;i++)
      cin>>patern[i];
   for(int i=1;i<=M;i++)
      cin>>niz[i];
   for(int i=1;i<=M;i++){
      sniz[i].poz=i;
      sniz[i].sv=niz[i];
   }
   sort(sniz+1,sniz+1+M,posv);
   int upok=K;
   for(int i=M;i>=1;i--){
      st[upok].cnt=1;
      st[upok].mlt=0;
      st[upok].rez=0;
      //on[sniz[i].poz+1].push_back(upok);
      upok++;

      st[upok].cnt=0;
      st[upok].mlt=stepen[sniz[i].poz];
      st[upok].rez=0;
      st[upok].on=false;
      int l=max(1,sniz[i].poz-N);
      //on[l].push_back(upok);
      //off[sniz[i].poz].push_back(upok);
   }
   for(int i=1;i<=M;i++){
     /* for(int j=0;j<on[i].size();j++)
         update(on[i][j],true);
      for(int j=0;j<off[i].size();j++)
         update(off[i][j],false);*/
      oduz[i]=st[1].rez;
   }
   cout<<0<<endl;
   return 0;
}

Compilation message

mat.cpp: In function 'int main()':
mat.cpp:69:11: warning: unused variable 'l' [-Wunused-variable]
   69 |       int l=max(1,sniz[i].poz-N);
      |           ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 8312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 9128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 8964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 211 ms 46424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 201 ms 45152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 180 ms 43660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 170 ms 43980 KB Output isn't correct
2 Halted 0 ms 0 KB -