제출 #1049786

#제출 시각아이디문제언어결과실행 시간메모리
1049786vjudge1Stove (JOI18_stove)C++17
100 / 100
35 ms7324 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; #define all(x) (x).begin(), (x).end() #define f first #define s second #define int long long #define yes cout<<"YES\n" #define no cout<<"NO\n" #define pb push_back #define fast ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) int mod = 100000000; typedef __gnu_pbds::tree<int, __gnu_pbds::null_type, less<int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> ordered_set; const int N=1e6+150; // int mind[N]; int d,n; vector<int> t; void init (int nn){ d=nn; t.assign (d, 0); } int sum (int r){ int result = 0; for (; r >= 0; r = (r & (r+1)) - 1) result += t[r]; return result; } void inc (int i, int delta){ for (; i < d; i = (i | (i+1))) t[i] += delta; } int sum (int l, int r){ return sum (r) - sum (l-1); } int ans=0,sze=0,k; vector<int>sz; // vector<int>cnt; vector<int>used; vector<vector<int>>g; void precalc(int v,int p){ sz[v]=1; for(auto k:g[v]){ if(k!=p and !used[k]){ precalc(k,v); sz[v]+=sz[k]; } } sze=max(sz[v],sze); } int centroid(int v,int p){ for(auto k:g[v]){ if(k!=p and sz[k]>sze/2 and !used[k]){ return centroid(k,v); } } return v; } void dfs(int v,int p,int len){ if(len>=d){ return; } // cout<<v<<' '<<sum(k-len-1)<<" "<<sum(d-len)<<" "<<len<<' '<<sum(k-len,d-len)<<'\n'; ans+=sum(k-len,d-len-1); for(auto to:g[v]){ if(to!=p and !used[to]){ dfs(to,v,len+1); } } } void update(int v,int p,int len){ if(len>=d){ return; } //cout<<k<<" "<<v<<" "<<len<<"\n"; inc(len,1); //cout<<k<<" "<<v<<" "<<len<<" "<<cnt[len]<<"\n"; for(auto to:g[v]){ if(to!=p and !used[to]){ update(to,v,len+1); } } } int h; void cent(int v){ sze=0; precalc(v,h); if(sze<=k) return; v=centroid(v,h); //cout<<v<<" "; inc(0,1); used[v]=1; // cout<<t[0]<<'\n'; for(auto to:g[v]){ if(to!=h and !used[to]){ dfs(to,v,1); update(to,v,1); } } for(int i=0;i<d;i++){ t[i]=0; } // cout<<sum(1,d)<<"\n"; for(auto to:g[v]){ if(to!=h and !used[to]){ h=v; cent(to); } } } void solve(){ int m,x,q,b=2,c=20,e=0,f=0,a=0,z; cin>>n>>k; vector<int>v(n); for(int i=0;i<n;i++){ cin>>v[i]; } if(k==1){ cout<<v[n-1]-v[0]+1<<"\n"; return; } multiset<pair<int,int>>s; for(int i=1;i<n;i++){ s.insert({v[i]-v[i-1],i-1}); if(k<=s.size()){ s.erase(s.begin()); } } c=0; int l=0; for(auto k:s){ // cout<<k.s<<" "; c+=v[k.s]-v[l]+1; l=k.s+1; } c+=v[n-1]-v[l]+1; cout<<c<<"\n"; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; // precalc(); // cin >> t; while(t--) { solve(); } }

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

stove.cpp: In function 'void solve()':
stove.cpp:128:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::multiset<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |         if(k<=s.size()){
      |            ~^~~~~~~~~~
stove.cpp:115:9: warning: unused variable 'm' [-Wunused-variable]
  115 |     int m,x,q,b=2,c=20,e=0,f=0,a=0,z;
      |         ^
stove.cpp:115:11: warning: unused variable 'x' [-Wunused-variable]
  115 |     int m,x,q,b=2,c=20,e=0,f=0,a=0,z;
      |           ^
stove.cpp:115:13: warning: unused variable 'q' [-Wunused-variable]
  115 |     int m,x,q,b=2,c=20,e=0,f=0,a=0,z;
      |             ^
stove.cpp:115:15: warning: unused variable 'b' [-Wunused-variable]
  115 |     int m,x,q,b=2,c=20,e=0,f=0,a=0,z;
      |               ^
stove.cpp:115:24: warning: unused variable 'e' [-Wunused-variable]
  115 |     int m,x,q,b=2,c=20,e=0,f=0,a=0,z;
      |                        ^
stove.cpp:6:11: warning: unused variable 'first' [-Wunused-variable]
    6 | #define f first
      |           ^~~~~
stove.cpp:115:28: note: in expansion of macro 'f'
  115 |     int m,x,q,b=2,c=20,e=0,f=0,a=0,z;
      |                            ^
stove.cpp:115:32: warning: unused variable 'a' [-Wunused-variable]
  115 |     int m,x,q,b=2,c=20,e=0,f=0,a=0,z;
      |                                ^
stove.cpp:115:36: warning: unused variable 'z' [-Wunused-variable]
  115 |     int m,x,q,b=2,c=20,e=0,f=0,a=0,z;
      |                                    ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...