제출 #739492

#제출 시각아이디문제언어결과실행 시간메모리
739492jelly1010Matching (CEOI11_mat)C++14
63 / 100
505 ms26244 KiB
#include <bits/stdc++.h> #define ll long long #define fi first #define se second #define maxi(a, base) a = max(a, base) #define mize(a, base) a = min(a, base) #define getbaseit(a, i) ((a) >> (i) & 1) #define FOR(i, a, base) for(int i=a, _n=base; i<=_n; ++i) #define FORD(i, a, base) for(int i=a, _n=base; i>=_n; --i) #define REP(i, _n) for(int i=0; i<_n; ++i) #define sz(a) ((int)(a).size()) #define all(a) a.baseegin(), a.end() #define pbase push_baseack #define mp make_pair #define ii pair<int, int> using namespace std; typedef long long hash_type; const int DIM = 2e5+5; const hash_type MOD1 = 1e9+7; const hash_type MOD2 = 1e9+7; const int base=1e4; struct segment_tree{ int hash1,hash2; int cnt; } aint[DIM*4]; pair <int,int> v[DIM]; int nrm[DIM]; int p1[DIM],p2[DIM]; vector <int> sol; int n,m,i,j,x; void update (int nod, int st, int dr, int poz, int val){ if (st == dr){ aint[nod].hash1 = aint[nod].hash2 = val; if (val) aint[nod].cnt = 1; else aint[nod].cnt = 0; return; } int mid = (st+dr)>>1; if (poz <= mid) update (nod<<1,st,mid,poz,val); else update ((nod<<1)|1,mid+1,dr,poz,val); int fiu_st = nod<<1, fiu_dr = (nod<<1)|1; aint[nod].hash1 = (1LL * aint[fiu_st].hash1 * p1[ aint[fiu_dr].cnt ] % MOD1 + aint[fiu_dr].hash1) % MOD1; aint[nod].hash2 = (1LL * aint[fiu_st].hash2 * p2[ aint[fiu_dr].cnt ] % MOD2 + aint[fiu_dr].hash2) % MOD2; aint[nod].cnt = aint[fiu_st].cnt + aint[fiu_dr].cnt; } int main (){ //ifstream cin ("date.in"); //ofstream cout ("date.out"); cin>>m>>n; int hash1 = 0, hash2 = 0; for (i=1;i<=m;i++){ cin>>x; hash1 = (1LL * hash1 * base % MOD1 + x) % MOD1; hash2 = (1LL * hash2 * base % MOD2 + x) % MOD2; } p1[0] = p2[0] = 1; for (i=1;i<=n;i++){ p1[i] = 1LL * p1[i-1] * base % MOD1; p2[i] = 1LL * p2[i-1] * base % MOD2; } for (i=1;i<=n;i++){ cin>>v[i].first; v[i].second = i; } sort (v+1,v+n+1); for (i=1;i<=n;i++) nrm[v[i].second] = i; for (i=1;i<m;i++) update (1,1,n,nrm[i],i); int sum1 = 0, sum2 = 0; for (i=0;i<m;i++){ sum1 = (sum1 + p1[i]) % MOD1; sum2 = (sum2 + p2[i]) % MOD2; } for (i=m;i<=n;i++){ /// adaug elem asta update (1,1,n,nrm[i],i); int val1 = (aint[1].hash1 - 1LL * sum1 * (i-m) % MOD1 + MOD1) % MOD1; int val2 = (aint[1].hash2 - 1LL * sum2 * (i-m) % MOD2 + MOD2) % MOD2; if (val1 == hash1) sol.push_back(i-m+1); /// sterg i-m+1 update (1,1,n,nrm[i-m+1],0); } cout<<sol.size()<<"\n"; for (auto it : sol) cout<<it<<" "; return 0; } //Jelly1010

컴파일 시 표준 에러 (stderr) 메시지

mat.cpp: In function 'int main()':
mat.cpp:106:13: warning: unused variable 'val2' [-Wunused-variable]
  106 |         int val2 = (aint[1].hash2 - 1LL * sum2 * (i-m) % MOD2 + MOD2) % MOD2;
      |             ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...