| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 320937 |
2020-11-10T09:58:08 Z |
egas |
Pilot (NOI19_pilot) |
C++14 |
|
22 ms |
5352 KB |
#include <bits/stdc++.h>
using namespace std;
long LOG[1005];
long POWW[31];
class SparseTable {
private:
long lookup[1005][(long) log2l(1005) + 1];
void buildSparseTable(long arr[], long n) {
for (long i = 0; i < n; i++)
lookup[i][0] = arr[i];
for (long j = 1;
(1 << j) <= n; j++) {
for (long 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 < long > & a) {
long num[a.size()];
for (long i = 0; i < a.size(); i++) {
num[i] = a[i];
}
buildSparseTable(num, a.size());
}
long query(long L, long R) {
L--;
R--;
long j = LOG[R - L + 1];
if (lookup[L][j] >= lookup[R - POWW[j] + 1][j])
return lookup[L][j];
else
return lookup[R - POWW[j] + 1][j];
}
};
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
long n;
cin >> n;
long m;
cin >> m;
vector < long > a(n);
for (long i = 0; i < n; i++) {
cin >> a[i];
}
vector < long > b(m);
for (long i = 0; i < m; i++) {
cin >> b[i];
}
for (int i = 0; i < 1005; i++) {
LOG[i] = (long) log2l(i);
}
for (int i = 0; i < 31; i++) {
POWW[i] = powl(2, i);
}
vector < long > diff(1005, 0);
SparseTable ST(a);
long * last = new long[1005];
long * frnt = new long[1005];
for (long i = 0; i < a.size(); i++) {
last[a[i]] = -1;
frnt[a[i]] = n;
}
for (long i = 0; i < n; i++) {
long ryt = 0;
long l = i;
long r = a.size() - 1;
if(i-1>=0 and a[i-1]>a[i]){
r=frnt[i-1];
}
while (l <= r) {
if (l == r) {
if (ST.query(i + 1, l + 1) <= a[i]) {
ryt = max(ryt, l);
}
break;
}
long m = (l + r) / 2;
if (ST.query(i + 1, m + 1) > a[i]) {
r = m - 1;
} else {
l = m + 1;
ryt = max(ryt, m);
}
}
frnt[i]=ryt;
ryt = ryt - i + 1;
ryt--;
long 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;
}
long 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 (long i = 1; i < diff.size(); i++) {
diff[i] += diff[i - 1];
}
for (long i = 0; i < b.size(); i++) {
cout << diff[b[i]] << '\n';
}
return 0;
}
Compilation message
pilot.cpp: In constructor 'SparseTable::SparseTable(std::vector<long int>&)':
pilot.cpp:29:28: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (long i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
pilot.cpp: In function 'int32_t main()':
pilot.cpp:78:24: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for (long i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
pilot.cpp:133:24: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for (long i = 1; i < diff.size(); i++) {
| ~~^~~~~~~~~~~~~
pilot.cpp:137:24: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for (long i = 0; i < b.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
3820 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
22 ms |
5100 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
22 ms |
5352 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
