제출 #957278

#제출 시각아이디문제언어결과실행 시간메모리
957278Nika533Rope (JOI17_rope)C++14
80 / 100
2527 ms91160 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) { for (int i=1; i<=m; i++) { int freq=pos[i].size(); vector<int> p; for (int oo=0; oo<pos[i].size(); oo++) { int j=pos[i][oo]; int o; if ((st+j)%2) o=j-1; else o=j+1; if (arr[o]!=0 && arr[o]!=i) p.pb(arr[o]); } for (auto x:p) update(1,1,m,x,-1); update(1,1,m,i,-freq); int mx=t[1]; ans[i]=min(ans[i],n-mx-freq); for (auto x:p) update(1,1,m,x,1); update(1,1,m,i,freq); } } void test_case() { cin>>n>>m; for (int i=1; i<=n; i++) { cin>>arr[i]; pos[arr[i]].pb(i); } build(1,1,m); 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(); }

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

rope.cpp:1: warning: ignoring '#pragma gcc diagnostic' [-Wunknown-pragmas]
    1 | #pragma gcc diagnostic "-std=c++1z"
      | 
rope.cpp: In function 'void solve(long long int)':
rope.cpp:39:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |           for (int oo=0; oo<pos[i].size(); oo++) {
      |                          ~~^~~~~~~~~~~~~~
rope.cpp: At global scope:
rope.cpp:65:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   65 | 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...