제출 #320908

#제출 시각아이디문제언어결과실행 시간메모리
320908egasPilot (NOI19_pilot)C++14
40 / 100
149 ms17768 KiB
#include <bits/stdc++.h> using namespace std; class SparseTable { private: int lookup[1000005][(int)log2l(1000005)+1]; void buildSparseTable(int arr[], int n) { for (int i = 0; i < n; i++) lookup[i][0] = arr[i]; for (int j = 1; (1 << j) <= n; j++) { for (int i = 0; (i + (1 << j) - 1) < n; i++) { if (lookup[i][j - 1] > lookup[i + (1 << (j - 1))][j - 1]) lookup[i][j] = lookup[i][j - 1]; else lookup[i][j] = lookup[i + (1 << (j - 1))][j - 1]; } } } public: SparseTable(vector<int> &a) { int num[a.size()]; for(int i = 0 ; i < a.size() ; i++) { num[i]=a[i]; } buildSparseTable(num,a.size()); } int query(int L, int R) { L--; R--; int j = (int)log2(R - L + 1); if (lookup[L][j] >= lookup[R - (1 << j) + 1][j]) return lookup[L][j]; else return lookup[R - (1 << j) + 1][j]; } }; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; int m; cin >> m; vector<int> a(n); for(int i = 0 ; i < n ; i++) { cin >> a[i]; } vector<int> b(m); for(int i = 0 ; i < m ; i++) { cin >> b[i]; } vector<int> diff(1000005,0); SparseTable ST(a); int *last=new int[1000005]; for(int i = 0 ; i < a.size() ; i++) { last[a[i]]=-1; } for(int i=0; i<n; i++) { int ryt=0; int l=i; int r=a.size()-1; while(l<=r) { if(l==r) { if(ST.query(i+1,l+1)<=a[i]) { ryt=max(ryt,l); } break; } int m=(l+r)/2; if(ST.query(i+1,m+1)>a[i]) { r=m-1; } else { l=m+1; ryt=max(ryt,m); } } ryt=ryt-i+1; ryt--; int left=1e9; l=last[a[i]]+1; r=i; while(l<=r) { if(l==r) { if(ST.query(l+1,i+1)<=a[i]) { left=min(left,l); } break; } int m=(l+r)/2; if(ST.query(m+1,i+1)>a[i]) { l=m+1; } else { r=m-1; left=min(left,m); } } left=i-left; last[a[i]]=i; diff[a[i]]+=((left+1)*(ryt+1)); } for(int i=1; i<diff.size(); i++) { diff[i]+=diff[i-1]; } for(int i = 0 ; i < b.size() ; i++) { cout << diff[b[i]] << '\n'; } return 0; }

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

pilot.cpp: In constructor 'SparseTable::SparseTable(std::vector<int>&)':
pilot.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int i = 0 ; i < a.size() ; i++) {
      |                         ~~^~~~~~~~~~
pilot.cpp: In function 'int32_t main()':
pilot.cpp:107:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int i = 0 ; i < a.size() ; i++) {
      |                     ~~^~~~~~~~~~
pilot.cpp:199:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |     for(int i=1; i<diff.size(); i++) {
      |                  ~^~~~~~~~~~~~
pilot.cpp:205:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  205 |     for(int i = 0 ; i < b.size() ; i++) {
      |                     ~~^~~~~~~~~~
#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...