이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |