| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 202669 |
2020-02-17T17:10:38 Z |
ismagilov |
Fire (JOI20_ho_t5) |
C++14 |
|
1000 ms |
262148 KB |
/**
* code generated by JHelper
* More info: https://github.com/AlexeyDmitriev/JHelper
* @author Azat Ismagilov
*/
/*.. ....
..',,'..............''...'''.','..
.';'.. ..',,'.
.'.. .';,.
.'. .:ol;. .';.
.. .cO00k:. .,.
.. .'...;k00Od' .'.
... .;xOkxdk00Od, ...
... .,x0000000Od;. ..
.' .cO00OOOOOOd;'... ...
.'. .;lxkOOOO00Okkxo:. .'.
.'. .cxOOOOO000000Ol. .'.
.'. .ck00OOd::oxOOOOl. .,.
''...,;''''''''':kKK0Od,. ..:xOo' .,.
';,;;;:,..........;lxOx:. .';' .''
'cc;.. .,;:,.. ...
,oc. .......... .',:;,.. ...
'o:. .,;;;,,,,;;;;;'. ..,;;,.. ...
';. ... .,::. .,::'. .'.
.. .',. ..;;'. ...
.. .',,;;,'. ':;'. .,.
.,::;,. ....... .';:'. .,,.
.;dOK0x;. . .':;. .,.
...,cdxdl;. ..,;;;cloddoc;. .,:,. .,.
. ...;cl:. ':ldxxdocccclol;. ..:;.',.
. .;llc;',c;. .,:,''';::;'. .. .;:;'
.:xdoxko,',. .,:. .;llc:ldl. .;c.
.lxdoxkd:''. .;:. .cxl'';od;. .. .,,
.:clool;.',. .:' .:dxolccl;. .::;,:'
.;::,.. .,. .;. .,:;:;,,;' .,;,:ol.
.. ',. .;. .',,,,,. .,:llc;.
.,' .,. .;lxxc'
.,;. .;. .;lxxc.
.. .;;. .:' .;cc,.
...';' .;;. .;:. ,:'
.;c:;. .. .,;. ....,;. .'.
.,lc,. .':,..,:,''....;c:;'':'.. .. .'.
.;:;. .,:' .::,,;;;;;..',;,..,,. .,. .'.
.'',,. .,;. .;, .'. ...
.'',,. .,;. ';. .,. .'.
.'... .;. .,,. .,' ..
.'. .;,. .::. .,' .
.'. .,;. ,c' .,' .'.
.'. .:' .,' .. .,'
''. ,;. ..................... .;' .:,
.,. .,;. ..'''''''''''''''''','. .,;. .::.
.,. ,;. .,;. .;,.
.,,. .:,. .;;. .''.
.,' .'. ... .,.
.'' .,.
.,'. .'.
.'. .*/
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>
#include <set>
#include <map>
#define int long long
#define ld long double
#define fs first
#define sc second
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define eb emplace_back
#define mp make_pair
#define len(v) ((int)v.size())
#define vc vector
#define pr pair
#define all(v) v.begin(), v.end()
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC optimize("unroll-loops")
using namespace std;
template<typename T, typename U>
inline ostream &operator<<(ostream &_out, const pair<T, U> &_p) {
_out << _p.first << ' ' << _p.second;
return _out;
}
template<typename T, typename U>
inline istream &operator>>(istream &_in, pair<T, U> &_p) {
_in >> _p.first >> _p.second;
return _in;
}
template<typename T>
inline ostream &operator<<(ostream &_out, const vector<T> &_v) {
if (_v.empty()) { return _out; }
_out << _v.front();
for (auto _it = ++_v.begin(); _it != _v.end(); ++_it) { _out << ' ' << *_it; }
return _out;
}
template<typename T>
inline istream &operator>>(istream &_in, vector<T> &_v) {
for (auto &_i : _v) { _in >> _i; }
return _in;
}
const int MAXN = 6e5;
const int INF = 1e9;
const int MOD = 1e9 + 7;
vc<pr<pr<int, int>, pr<int, int>>> lefts, rights;
void add_segment(int l1, int r1, int l2, int r2, int value) {
//cout << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << ' ' << value << endl;
if (r1 - l1 >= r2 - l2) {
for (int i = l1; i <= r1; i++) {
lefts.pb({{i, value},
{l2 - i, r2 - i}});
}
} else {
for (int i = l2; i <= r2; i++) {
rights.pb({{i, value},
{i - r1, i - l1}});
}
}
}
int n;
int t[MAXN];
void init(int nn) {
n = nn;
fill(t, t + n, 0);
}
void upd(int v, int x) {
for (; v < n; v = (v | (v + 1))) {
t[v] += x;
}
}
int get(int v) {
int ans = 0;
for (; v >= 0; v = (v & (v + 1)) - 1) {
ans += t[v];
}
return ans;
}
int get(int l, int r) {
return get(r) - get(l - 1);
}
class pozhar {
public:
void solve(std::istream &in, std::ostream &out) {
int n, q;
in >> n >> q;
vc<int> s(n);
in >> s;
set<int> limiters;
limiters.insert(-1);
limiters.insert(n);
vc<pr<int, int>> dds;
for (int i = 0; i < n; i++) {
dds.pb({s[i], i});
}
sort(all(dds));
reverse(all(dds));
for (auto v : dds) {
auto r = (*limiters.lower_bound(v.sc)) - 1;
auto l = (*prev(limiters.lower_bound(v.sc))) + 1;
if (l <= v.sc && v.sc <= r) {
add_segment(l, v.sc, v.sc, r, v.fs);
}
limiters.insert(v.sc);
}
/*
cout << "lefts\n";
for (auto v : lefts) {
cout << v << endl;
}
cout << "rights\n";
for (auto v : rights) {
cout << v << endl;
}
*/
vc<int> ans(q);
vc<pr<int, pr<int, int>>> que(q);
vc<vc<int>> bylen(n + 2);
int i = 0;
for (auto &v : que) {
in >> v.fs >> v.sc;
v.sc.fs--, v.sc.sc--;
bylen[v.fs].pb(i);
i++;
}
{
int maxi = 0;
for (int i = 0; i < n; i++) {
maxi = max(maxi, s[i]);
rights.pb({{i, maxi},
{i + 1, n}});
}
}
{
vc<vc<pr<int, int>>> gr(n + 2);
for (auto v : lefts) {
gr[v.sc.fs].pb(v.fs);
v.fs.sc *= -1;
gr[v.sc.sc + 1].pb(v.fs);
}
init(2 * n);
for (int i = 0; i <= n; i++) {
for (auto d : gr[i]) {
upd(d.fs + n, d.sc);
}
for (auto d : bylen[i]) {
ans[d] += get(que[d].sc.fs - i + n, que[d].sc.sc - i + n);
}
}
}
{
vc<vc<pr<int, int>>> gr(n + 2);
for (auto v : rights) {
gr[v.sc.fs].pb(v.fs);
v.fs.sc *= -1;
gr[v.sc.sc + 1].pb(v.fs);
}
init(2 * n);
for (int i = 0; i <= n; i++) {
for (auto d : gr[i]) {
upd(d.fs, d.sc);
}
for (auto d : bylen[i]) {
ans[d] += get(que[d].sc.fs, que[d].sc.sc);
}
}
}
for (auto v : ans) {
out << v << '\n';
}
}
};
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
pozhar solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
504 KB |
Output is correct |
| 3 |
Correct |
5 ms |
504 KB |
Output is correct |
| 4 |
Correct |
5 ms |
504 KB |
Output is correct |
| 5 |
Correct |
5 ms |
504 KB |
Output is correct |
| 6 |
Correct |
5 ms |
504 KB |
Output is correct |
| 7 |
Correct |
5 ms |
504 KB |
Output is correct |
| 8 |
Correct |
5 ms |
504 KB |
Output is correct |
| 9 |
Correct |
5 ms |
504 KB |
Output is correct |
| 10 |
Correct |
6 ms |
504 KB |
Output is correct |
| 11 |
Correct |
5 ms |
504 KB |
Output is correct |
| 12 |
Correct |
5 ms |
504 KB |
Output is correct |
| 13 |
Correct |
5 ms |
504 KB |
Output is correct |
| 14 |
Correct |
5 ms |
500 KB |
Output is correct |
| 15 |
Correct |
5 ms |
504 KB |
Output is correct |
| 16 |
Correct |
5 ms |
504 KB |
Output is correct |
| 17 |
Correct |
5 ms |
504 KB |
Output is correct |
| 18 |
Correct |
5 ms |
504 KB |
Output is correct |
| 19 |
Correct |
5 ms |
504 KB |
Output is correct |
| 20 |
Correct |
5 ms |
504 KB |
Output is correct |
| 21 |
Correct |
5 ms |
504 KB |
Output is correct |
| 22 |
Correct |
5 ms |
504 KB |
Output is correct |
| 23 |
Correct |
5 ms |
504 KB |
Output is correct |
| 24 |
Correct |
5 ms |
504 KB |
Output is correct |
| 25 |
Correct |
5 ms |
504 KB |
Output is correct |
| 26 |
Correct |
6 ms |
504 KB |
Output is correct |
| 27 |
Correct |
6 ms |
504 KB |
Output is correct |
| 28 |
Correct |
5 ms |
504 KB |
Output is correct |
| 29 |
Correct |
6 ms |
504 KB |
Output is correct |
| 30 |
Correct |
5 ms |
504 KB |
Output is correct |
| 31 |
Correct |
5 ms |
504 KB |
Output is correct |
| 32 |
Correct |
5 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
931 ms |
239896 KB |
Output is correct |
| 3 |
Correct |
925 ms |
239668 KB |
Output is correct |
| 4 |
Correct |
893 ms |
230604 KB |
Output is correct |
| 5 |
Correct |
911 ms |
235452 KB |
Output is correct |
| 6 |
Correct |
941 ms |
242284 KB |
Output is correct |
| 7 |
Correct |
951 ms |
255696 KB |
Output is correct |
| 8 |
Correct |
920 ms |
240412 KB |
Output is correct |
| 9 |
Correct |
922 ms |
249248 KB |
Output is correct |
| 10 |
Correct |
876 ms |
233296 KB |
Output is correct |
| 11 |
Correct |
926 ms |
238720 KB |
Output is correct |
| 12 |
Correct |
938 ms |
243176 KB |
Output is correct |
| 13 |
Correct |
949 ms |
242820 KB |
Output is correct |
| 14 |
Execution timed out |
1008 ms |
257480 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Execution timed out |
1114 ms |
262124 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
302 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
504 KB |
Output is correct |
| 3 |
Correct |
5 ms |
504 KB |
Output is correct |
| 4 |
Correct |
5 ms |
504 KB |
Output is correct |
| 5 |
Correct |
5 ms |
504 KB |
Output is correct |
| 6 |
Correct |
5 ms |
504 KB |
Output is correct |
| 7 |
Correct |
5 ms |
504 KB |
Output is correct |
| 8 |
Correct |
5 ms |
504 KB |
Output is correct |
| 9 |
Correct |
5 ms |
504 KB |
Output is correct |
| 10 |
Correct |
6 ms |
504 KB |
Output is correct |
| 11 |
Correct |
5 ms |
504 KB |
Output is correct |
| 12 |
Correct |
5 ms |
504 KB |
Output is correct |
| 13 |
Correct |
5 ms |
504 KB |
Output is correct |
| 14 |
Correct |
5 ms |
500 KB |
Output is correct |
| 15 |
Correct |
5 ms |
504 KB |
Output is correct |
| 16 |
Correct |
5 ms |
504 KB |
Output is correct |
| 17 |
Correct |
5 ms |
504 KB |
Output is correct |
| 18 |
Correct |
5 ms |
504 KB |
Output is correct |
| 19 |
Correct |
5 ms |
504 KB |
Output is correct |
| 20 |
Correct |
5 ms |
504 KB |
Output is correct |
| 21 |
Correct |
5 ms |
504 KB |
Output is correct |
| 22 |
Correct |
5 ms |
504 KB |
Output is correct |
| 23 |
Correct |
5 ms |
504 KB |
Output is correct |
| 24 |
Correct |
5 ms |
504 KB |
Output is correct |
| 25 |
Correct |
5 ms |
504 KB |
Output is correct |
| 26 |
Correct |
6 ms |
504 KB |
Output is correct |
| 27 |
Correct |
6 ms |
504 KB |
Output is correct |
| 28 |
Correct |
5 ms |
504 KB |
Output is correct |
| 29 |
Correct |
6 ms |
504 KB |
Output is correct |
| 30 |
Correct |
5 ms |
504 KB |
Output is correct |
| 31 |
Correct |
5 ms |
504 KB |
Output is correct |
| 32 |
Correct |
5 ms |
504 KB |
Output is correct |
| 33 |
Execution timed out |
1063 ms |
237756 KB |
Time limit exceeded |
| 34 |
Halted |
0 ms |
0 KB |
- |
