Submission #957268

#TimeUsernameProblemLanguageResultExecution timeMemory
957268Nika533Rope (JOI17_rope)C++14
0 / 100
13 ms29528 KiB
#pragma gcc diagnostic "-std=c++1z" #include <bits/stdc++.h> #define int long long #define pb push_back #define f first #define s second #define MOD 1000000007 #define pii pair<int,int> #define all(x) (x).begin(),(x).end() #define allr(x) (x).rbegin(),(x).rend() using namespace std; const int N=1e6+5; int n,m,T,k,arr[N],ans[N]; int t[N*4]; vector<int> pos[N]; void build(int v, int tl, int tr) { if (tl==tr) { t[v]=pos[tl].size(); return; } int mid=(tl+tr)/2; build(v*2,tl,mid); build(v*2+1,mid+1,tr); t[v]=max(t[v*2],t[v*2+1]); } void update(int v, int tl, int tr, int ind, int val) { if (ind<tl || ind>tr) return; if (tl==tr) { t[v]+=val; return; } int mid=(tl+tr)/2; update(v*2,tl,mid,ind,val); update(v*2+1,mid+1,tr,ind,val); t[v]=max(t[v*2],t[v*2+1]); } void solve(int st) { build(1,1,m); for (int i=1; i<=m; i++) { int freq=pos[i].size(); vector<int> p; for (auto j:pos[i]) { int o; if ((st+j)%2) o=j-1; else o=j+1; if (arr[o]) p.pb(arr[o]); p.pb(arr[j]); } for (auto x:p) update(1,1,m,x,-1); int mx=t[1]; ans[i]=min(ans[i],n-mx-freq); for (auto x:p) update(1,1,m,x,1); } } void test_case() { cin>>n>>m; for (int i=1; i<=n; i++) { cin>>arr[i]; pos[arr[i]].pb(i); } for (int i=1; i<=m; i++) ans[i]=1e9; solve(0); solve(1); for (int i=1; i<=m; i++) cout<<ans[i]<<endl; } main () { ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0); T=1; while (T--) test_case(); }

Compilation message (stderr)

rope.cpp:1: warning: ignoring '#pragma gcc diagnostic' [-Wunknown-pragmas]
    1 | #pragma gcc diagnostic "-std=c++1z"
      | 
rope.cpp:63:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   63 | main () {
      | ^~~~
#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...