제출 #586484

#제출 시각아이디문제언어결과실행 시간메모리
586484wdjpng모임들 (IOI18_meetings)C++17
17 / 100
170 ms154024 KiB
#include "meetings.h" #include <bits/stdc++.h> #define int long long #define all(a) a.begin(), a.end() #define rep(i,n) for(int i = 0; i<n; i++) using namespace std; struct s { int m=0,l=0,r=0, ar=0; }; s unite(s s1, s s2) { s res; res.ar=s1.ar+s2.ar; res.m=max({s1.m,s2.m,s1.r+s2.l}); res.l=s1.l; res.r=s2.r; if(s1.l==s1.ar) res.l+=s2.l; if(s2.r==s2.ar) res.r+=s1.r; return res; } s def=s(); int N = 100000; vector<s>T(4*N); s update(int i, int l, int r, int ui, int uv) { if(l>ui||r<=ui) return T[i]; if(l+1==r) return T[i]=s({uv,uv,uv,1}); return T[i] = unite(update(2*i,l,(l+r)/2,ui,uv), update(2*i+1,(l+r)/2,r,ui,uv)); } s query(int i, int l, int r, int ql, int qr) { if(l>=qr||r<=ql) return def; if(l>=ql&&r<=qr) return T[i]; return unite(query(2*i,l,(l+r)/2,ql,qr),query(2*i+1,(l+r)/2,r,ql,qr)); } vector<int> minimum_costs(vector<signed> H,vector<signed> L, vector<signed> R) { int n = H.size(); if(n>5000) { rep(i,n) update(1,0,n,i,H[i]==1); vector<int>C(L.size()); rep(cq, L.size()) C[cq]=2*(R[cq] - L[cq] + 1) - query(1,0,n,L[cq], R[cq]+1).m; return C; } else { vector<vector<int>>lef(n, vector<int>(n)), ri(n, vector<int>(n)); rep(i,n) { int sum=0; vector<int>v, occ; for(int j = i; j < n; j++) { sum+=H[j]; int c = 1; while (v.size()&&v[v.size()-1]<H[j]) { sum+=H[j]-v[v.size()-1]; c+=occ[occ.size()-1]; v.pop_back(); occ.pop_back(); } if(v.size()&&v[v.size()-1]==H[j]) occ[occ.size()-1]+=c; else {v.push_back(H[j]); occ.push_back(c);} lef[i][j]=sum; } } for(int i = n-1; i >= 0; i--) { int sum=0; vector<int>v, occ; for(int j = i; j >= 0; j--) { sum+=H[j]; int c = 1; while (v.size()&&v[v.size()-1]<H[j]) { sum+=H[j]-v[v.size()-1]; c+=occ[occ.size()-1]; v.pop_back(); occ.pop_back(); } if(v.size()&&v[v.size()-1]==H[j]) occ[occ.size()-1]+=c; else {v.push_back(H[j]); occ.push_back(c);} ri[i][j]=sum; } } vector<int>c(L.size()); rep(i,L.size()) { int minn=1e18; for(int j = L[i]; j <= R[i]; j++) { minn=min(minn, lef[L[i]][j]+ri[R[i]][j]-H[j]); } c[i]=minn; } return c; } }

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

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:7:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(i,n) for(int i = 0; i<n; i++)
......
   54 |     rep(cq, L.size()) C[cq]=2*(R[cq] - L[cq] + 1) - query(1,0,n,L[cq], R[cq]+1).m;
      |         ~~~~~~~~~~~~              
meetings.cpp:54:5: note: in expansion of macro 'rep'
   54 |     rep(cq, L.size()) C[cq]=2*(R[cq] - L[cq] + 1) - query(1,0,n,L[cq], R[cq]+1).m;
      |     ^~~
meetings.cpp:7:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(i,n) for(int i = 0; i<n; i++)
......
  100 |       rep(i,L.size())
      |           ~~~~~~~~~~              
meetings.cpp:100:7: note: in expansion of macro 'rep'
  100 |       rep(i,L.size())
      |       ^~~
#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...