| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 202631 |
2020-02-17T11:29:57 Z |
SamAnd |
Fire (JOI20_ho_t5) |
C++17 |
|
329 ms |
22512 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
struct ban
{
int t, l, r;
};
int n, m;
int s[N];
ban b[N];
int ss[N];
void solv1()
{
for (int i = 1; i <= m; ++i)
{
for (int j = 1; j <= n; ++j)
ss[j] = s[j];
for (int ii = 0; ii < b[i].t; ++ii)
{
for (int j = n; j >= 1; --j)
ss[j] = max(ss[j], ss[j - 1]);
}
long long ans = 0;
for (int j = b[i].l; j <= b[i].r; ++j)
ans += ss[j];
printf("%lld\n", ans);
}
}
int t[N * 4];
void bil(int tl, int tr, int pos)
{
if (tl == tr)
{
t[pos] = s[tl];
return;
}
int m = (tl + tr) / 2;
bil(tl, m, pos * 2);
bil(m + 1, tr, pos * 2 + 1);
t[pos] = max(t[pos * 2], t[pos * 2 + 1]);
}
int qry(int tl, int tr, int l, int r, int pos)
{
if (tl == l && tr == r)
return t[pos];
int m = (tl + tr) / 2;
if (r <= m)
return qry(tl, m, l, r, pos * 2);
if (l > m)
return qry(m + 1, tr, l, r, pos * 2 + 1);
return max(qry(tl, m, l, m, pos * 2),
qry(m + 1, tr, m + 1, r, pos * 2 + 1));
}
long long p[N];
void solv2()
{
bil(1, n, 1);
for (int i = 1; i <= n; ++i)
s[i] = qry(1, n, max(1, i - b[1].t), i, 1);
for (int i = 1; i <= n; ++i)
p[i] = p[i - 1] + s[i];
for (int i = 1; i <= m; ++i)
printf("%lld\n", p[b[i].r] - p[b[i].l - 1]);
}
void solv3()
{
bil(1, n, 1);
for (int i = 1; i <= m; ++i)
{
printf("%d\n", qry(1, n, max(1, b[i].l - b[i].t), b[i].l, 1));
}
}
int t1[N * 4];
void ubd1(int tl, int tr, int x, int pos)
{
if (tl == tr)
{
t1[pos] = 1;
return;
}
int m = (tl + tr) / 2;
if (x <= m)
ubd1(tl, m, x, pos * 2);
else
ubd1(m + 1, tr, x, pos * 2 + 1);
t1[pos] = t1[pos * 2] + t1[pos * 2 + 1];
}
int qry1(int tl, int tr, int l, int r, int pos)
{
if (l > r)
return 0;
if (tl == l && tr == r)
return t1[pos];
int m = (tl + tr) / 2;
return qry1(tl, m, l, min(m, r), pos * 2) +
qry1(m + 1, tr, max(m + 1, l), r, pos * 2 + 1);
}
int ans[N];
int u2[N];
vector<int> v[N];
vector<int> q[N];
void solv4()
{
for (int i = 1; i <= n; ++i)
{
u2[i] = u2[i - 1];
if (s[i] == 2)
u2[i] = i;
}
for (int i = 1; i <= n; ++i)
{
if (u2[i])
v[i - u2[i]].push_back(i);
}
for (int i = 1; i <= m; ++i)
{
q[b[i].t].push_back(i);
}
for (int i = 0; i <= n; ++i)
{
for (int j = 0; j < v[i].size(); ++j)
{
int x = v[i][j];
ubd1(1, n, x, 1);
}
for (int j = 0; j < q[i].size(); ++j)
{
int x = q[i][j];
ans[x] = qry1(1, n, b[x].l, b[x].r, 1) + (b[x].r - b[x].l + 1);
}
}
for (int i = 1; i <= m; ++i)
printf("%d\n", ans[i]);
}
int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", &s[i]);
for (int i = 1; i <= m; ++i)
{
scanf("%d%d%d", &b[i].t, &b[i].l, &b[i].r);
}
solv4();
return 0;
}
Compilation message
ho_t5.cpp: In function 'void solv4()':
ho_t5.cpp:132:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v[i].size(); ++j)
~~^~~~~~~~~~~~~
ho_t5.cpp:137:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < q[i].size(); ++j)
~~^~~~~~~~~~~~~
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:150:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
ho_t5.cpp:152:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &s[i]);
~~~~~^~~~~~~~~~~~~
ho_t5.cpp:155:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &b[i].t, &b[i].l, &b[i].r);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9720 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9720 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9720 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
316 ms |
22264 KB |
Output is correct |
| 2 |
Correct |
329 ms |
22128 KB |
Output is correct |
| 3 |
Correct |
312 ms |
22384 KB |
Output is correct |
| 4 |
Correct |
317 ms |
22400 KB |
Output is correct |
| 5 |
Correct |
307 ms |
22512 KB |
Output is correct |
| 6 |
Correct |
311 ms |
22128 KB |
Output is correct |
| 7 |
Correct |
311 ms |
22292 KB |
Output is correct |
| 8 |
Correct |
310 ms |
22256 KB |
Output is correct |
| 9 |
Correct |
303 ms |
22312 KB |
Output is correct |
| 10 |
Correct |
307 ms |
22196 KB |
Output is correct |
| 11 |
Correct |
305 ms |
22456 KB |
Output is correct |
| 12 |
Correct |
314 ms |
22304 KB |
Output is correct |
| 13 |
Correct |
301 ms |
22320 KB |
Output is correct |
| 14 |
Correct |
315 ms |
22404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9720 KB |
Output isn't correct |
