結果
| 問題 | No.2942 Sigma Music Game Level Problem |
| ユーザー |
 ルク
|
| 提出日時 | 2024-10-18 22:43:04 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 22,780 bytes |
| コンパイル時間 | 8,421 ms |
| コンパイル使用メモリ | 345,632 KB |
| 実行使用メモリ | 160,704 KB |
| 最終ジャッジ日時 | 2024-11-07 22:02:33 |
| 合計ジャッジ時間 | 17,327 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 3 ms
5,248 KB |
| testcase_02 | AC | 3 ms
5,248 KB |
| testcase_03 | AC | 3 ms
5,248 KB |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | AC | 3 ms
5,248 KB |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | TLE | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
ソースコード
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#if __has_include("./cpp-dump/cpp-dump.hpp")
#include "./cpp-dump/cpp-dump.hpp"
#endif
#include <chrono>
#include <unistd.h>
#include <random>
using namespace std;
using namespace chrono;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using mint = modint998244353;
using MINT = modint1000000007;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
constexpr double pi = 3.141592653589793;
constexpr ll smallMOD = 998244353;
constexpr ll bigMOD = 1000000007;
constexpr ll INF = 1LL << 60;
constexpr ll dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr ll dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
// init.
struct Init
{
Init()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
}
} init;
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec)
{
os << "[";
rep(i, vec.size())
{
os << vec[i];
if (i != vec.size() - 1)
os << ", ";
}
os << "]";
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<T>> &vec)
{
os << "[";
rep(i, vec.size())
{
os << vec[i];
if (i != vec.size() - 1)
os << ", ";
}
os << "]";
return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &pair_var)
{
os << "(" << pair_var.first << ", " << pair_var.second << ")";
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &st)
{
os << "{";
for (auto itr = st.begin(); itr != st.end(); ++itr)
{
os << *itr;
if (next(itr) != st.end())
os << ", ";
}
os << "}";
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &st)
{
os << "{";
for (auto itr = st.begin(); itr != st.end(); ++itr)
{
os << *itr;
if (next(itr) != st.end())
os << ", ";
}
os << "}";
return os;
}
template <class T>
bool chmax(T &a, T b)
{
if (a < b)
{
a = b;
return 1;
}
return 0;
}
template <class T>
bool chmin(T &a, T b)
{
if (b < a)
{
a = b;
return 1;
}
return 0;
}
// functions.
// Math.
void calc_divisors(ll N, vector<ll> &res)
{
for (ll i = 1; i * i <= N; ++i)
{
if (N % i != 0)
continue;
res.push_back(i);
if (N / i != i)
res.push_back(N / i);
}
sort(res.begin(), res.end());
}
void recursive_comb(vector<ll> indexes, ll s, ll rest, function<void(vector<ll>)> f)
{
if (rest == 0)
{
f(indexes);
}
else
{
if (s < 0)
return;
recursive_comb(indexes, s - 1, rest, f);
indexes[rest - 1] = s;
recursive_comb(indexes, s - 1, rest - 1, f);
}
}
void foreach_comb(ll n, ll k, function<void(vector<ll>)> f)
{
vector<ll> indexes(k);
recursive_comb(indexes, n - 1, k, f);
}
void prime_factorize(ll N, vector<pair<ll, ll>> &res)
{
for (ll p = 2; p * p <= N; ++p)
{
if (N % p != 0)
continue;
ll e = 0;
while (N % p == 0)
{
++e;
N /= p;
}
res.emplace_back(p, e);
}
if (N != 1)
{
res.emplace_back(N, 1);
}
}
ll repeated_squaring(ll x, ll y, ll z = smallMOD)
{
ll ans = 1;
bitset<64> bits(y);
string bit_str = bits.to_string();
reverse(all(bit_str));
rep(i, 64)
{
if (bit_str[i] == '1')
ans = ans * x % z;
x = x * x % z;
}
return ans;
}
// String.
bool isPalindrome(string str)
{
ll low = 0;
ll high = str.length() - 1;
while (low < high)
{
if (str[low] != str[high])
{
return false;
}
low++;
high--;
}
return true;
}
map<char, ll> alphabetHash = {
{'a', 2},
{'b', 3},
{'c', 5},
{'d', 7},
{'e', 11},
{'f', 13},
{'g', 17},
{'h', 19},
{'i', 23},
{'j', 29},
{'k', 31},
{'l', 37},
{'m', 41},
{'n', 43},
{'o', 47},
{'p', 53},
{'q', 59},
{'r', 61},
{'s', 67},
{'t', 71},
{'u', 73},
{'v', 79},
{'w', 83},
{'x', 89},
{'y', 97},
{'z', 101},
};
void split(vector<string> &elems, const string &s, char delim)
{
stringstream ss(s);
string item;
while (getline(ss, item, delim))
{
elems.push_back(item);
}
}
ll string_mod(string s, ll mod)
{
ll rest = 0;
for (char c : s)
{
ll v = c - '0';
rest = (rest * 10 + v) % mod;
}
return rest;
}
// algorithms.
pair<pair<ll, ll>, pair<ll, ll>> maxAndMinSubarraySum(const vector<ll> &nums)
{
ll maxSum = nums[0];
ll minSum = nums[0];
ll maxStart = 0;
ll maxEnd = 0;
ll minStart = 0;
ll minEnd = 0;
ll currentMaxSum = nums[0];
ll currentMinSum = nums[0];
ll tempMaxStart = 0;
ll tempMinStart = 0;
for (ll i = 1; i < nums.size(); ++i)
{
if (currentMaxSum < 0)
{
currentMaxSum = nums[i];
tempMaxStart = i;
}
else
{
currentMaxSum += nums[i];
}
if (currentMaxSum > maxSum)
{
maxSum = currentMaxSum;
maxStart = tempMaxStart;
maxEnd = i;
}
if (currentMinSum > 0)
{
currentMinSum = nums[i];
tempMinStart = i;
}
else
{
currentMinSum += nums[i];
}
if (currentMinSum < minSum)
{
minSum = currentMinSum;
minStart = tempMinStart;
minEnd = i;
}
}
return make_pair(make_pair(maxStart, maxEnd), make_pair(minStart, minEnd));
}
// array.
vector<string> RotateVectorString(vector<string> A, bool clockwise = false, char leading = 0)
{
ll N = A.size();
if (N == 0)
return A;
ll M = 0;
rep(i, N)
{
M = max(M, (ll)A[i].size());
}
vector<string> B(M, string(N, leading));
rep(i, N)
{
rep(j, A[i].size())
{
if (clockwise)
{
B[j][N - 1 - i] = A[i][j];
}
else
{
B[M - 1 - j][i] = A[i][j];
}
}
}
return B;
}
// struct.
// Data structure.
struct CumulativeSum2D
{
vector<vector<ll>> data;
CumulativeSum2D(vector<vector<ll>> &source)
{
ll h = source.size();
ll w = 0;
if (h != 0)
w = source[0].size();
data.resize(h + 1, vector<ll>(w + 1, 0));
rep(i, h) rep(j, w) data[i + 1][j + 1] = source[i][j];
rep(i, h + 1) rep(j, w) data[i][j + 1] += data[i][j];
rep(i, h) rep(j, w + 1) data[i + 1][j] += data[i][j];
}
ll query(ll x1, ll y1, ll x2, ll y2)
{
return data[x2][y2] - data[x1][y2] - data[x2][y1] + data[x1][y1];
}
};
struct UnionFind
{
vector<ll> parent;
vector<ll> parentSize;
UnionFind(ll N)
{
rep(i, N + 1)
{
parent.push_back(i);
parentSize.push_back(1);
}
}
ll root(ll x)
{
if (parent[x] == x)
return x;
parent[x] = root(parent[x]);
return parent[x];
}
void unite(ll x, ll y)
{
x = root(x);
y = root(y);
if (x == y)
return;
if (parentSize[x] <= parentSize[y])
{
parent[x] = y;
parentSize[y] += parentSize[x];
}
else
{
parent[y] = x;
parentSize[x] += parentSize[y];
}
}
bool same(ll x, ll y)
{
return root(x) == root(y);
}
ll size(ll x)
{
return parentSize[root(x)];
}
};
// Math.
struct NCR
{
ll max = 510000, mod = 0;
vector<ll> fact, inv, inv_fact;
NCR(ll mod = 998244353)
{
this->mod = mod;
fact.resize(max);
inv.resize(max);
inv_fact.resize(max);
fact[0] = 1;
fact[1] = 1;
inv[0] = 1;
inv[1] = 1;
inv_fact[0] = 1;
inv_fact[1] = 1;
for (ll i = 2; i < max; i++)
{
fact[i] = fact[i - 1] * i % mod;
inv[i] = mod - inv[mod % i] * (mod / i) % mod;
inv_fact[i] = inv_fact[i - 1] * inv[i] % mod;
}
}
ll nCr(ll n, ll r)
{
ll x = fact[n];
ll y = inv_fact[n - r];
ll z = inv_fact[r];
if (n < r)
return 0;
if (n < 0 || r < 0)
return 0;
return x * ((y * z) % mod) % mod;
}
};
// Graph.
struct Edge
{
ll to;
ll cost;
Edge(ll to, ll cost) : to(to), cost(cost) {}
bool operator>(const Edge &e) const
{
return cost > e.cost;
}
};
struct Graph
{
vector<vector<Edge>> g;
Graph(ll n)
{
g.resize(n);
}
ll size()
{
return g.size();
}
void add_edge(ll from, ll to, ll cost = 1)
{
g[from].push_back(Edge(to, cost));
g[to].push_back(Edge(from, cost));
}
void add_directed_edge(ll from, ll to, ll cost = 1)
{
g[from].push_back(Edge(to, cost));
}
pair<ll, vector<ll>> tree_diameter()
{
function<pair<ll, ll>(ll, ll)> dfs = [&](ll v, ll p) -> pair<ll, ll>
{
pair<ll, ll> res = {0, v};
for (auto e : g[v])
{
if (e.to == p)
continue;
auto [d, u] = dfs(e.to, v);
d += e.cost;
if (res.first < d)
{
res.first = d;
res.second = u;
}
}
return res;
};
auto [d, u] = dfs(0, -1);
auto [d2, v] = dfs(u, -1);
vector<ll> path;
function<void(ll, ll, ll)> get_path = [&](ll v, ll p, ll u)
{
if (v == u)
{
path.push_back(v);
return;
}
for (auto e : g[v])
{
if (e.to == p)
continue;
get_path(e.to, v, u);
if (!path.empty())
{
path.push_back(v);
return;
}
}
};
get_path(u, -1, v);
return {d2, path};
}
vector<Edge> &operator[](ll v)
{
return g[v];
}
};
struct Dijkstra
{
vector<ll> dist;
vector<ll> prev;
// dijkstraを構築
Dijkstra(Graph &g, ll s)
{
ll n = g.size();
dist.assign(n, INF);
prev.assign(n, -1);
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
dist[s] = 0;
pq.emplace(dist[s], s);
while (!pq.empty())
{
auto p = pq.top();
pq.pop();
ll v = p.second;
if (dist[v] < p.first)
continue;
for (auto &e : g[v])
{
if (dist[e.to] > dist[v] + e.cost)
{
dist[e.to] = dist[v] + e.cost;
prev[e.to] = v;
pq.emplace(dist[e.to], e.to);
}
}
}
}
// 最小コストを求める
ll get_cost(ll to)
{
return dist[to];
}
// 最短経路を求める
vector<ll> get_path(ll to)
{
vector<ll> get_path;
for (ll i = to; i != -1; i = prev[i])
{
get_path.push_back(i);
}
reverse(get_path.begin(), get_path.end());
return get_path;
}
// 到達可能か調べる
bool cango(ll to)
{
return (dist[to] != INF);
}
};
struct Bellman_ford
{
vector<ll> dist;
vector<ll> prev;
ll start;
ll size;
bool cl = false;
// bellman_fordを構築
Bellman_ford(Graph &g, ll s)
{
start = s;
ll n = g.size();
size = n;
dist.assign(n, INF);
prev.assign(n, -1);
vector<ll> counts(n);
vector<bool> inqueue(n);
queue<ll> q;
dist[s] = 0;
q.push(s);
inqueue[s] = true;
while (!q.empty())
{
ll from = q.front();
q.pop();
inqueue[from] = false;
for (auto &e : g[from])
{
ll d = dist[from] + e.cost;
if (d < dist[e.to])
{
dist[e.to] = d;
prev[e.to] = from;
if (!inqueue[e.to])
{
q.push(e.to);
inqueue[e.to] = true;
++counts[e.to];
if (n < counts[e.to])
cl = true;
}
}
}
}
}
// 最小コストを求める
ll get_cost(ll to)
{
return dist[to];
}
// 最短経路を求める
vector<ll> get_path(ll to)
{
vector<ll> path;
if (dist[to] != INF)
{
for (ll i = to; i != -1; i = prev[i])
{
path.push_back(i);
}
reverse(path.begin(), path.end());
}
return path;
}
// 到達可能か調べる
bool cango(ll to)
{
return (dist[to] != INF);
}
// 閉路の有無を調べる
bool closed()
{
return cl;
}
};
struct Warshall_floyd
{
vector<vector<ll>> d;
vector<vector<ll>> next;
bool cl = false;
// warshall_floydを構築
Warshall_floyd(Graph &g)
{
ll n = g.size();
d.resize(n, vector<ll>(n, INF));
next.resize(n, vector<ll>(n, -1));
for (ll i = 0; i < n; i++)
{
d[i][i] = 0;
}
for (ll i = 0; i < n; i++)
{
for (auto e : g[i])
{
d[i][e.to] = e.cost;
next[i][e.to] = e.to;
}
}
for (ll k = 0; k < n; ++k)
{
for (ll i = 0; i < n; ++i)
{
for (ll j = 0; j < n; ++j)
{
if (d[i][j] > d[i][k] + d[k][j])
{
d[i][j] = d[i][k] + d[k][j];
next[i][j] = next[i][k];
}
}
}
}
for (ll i = 0; i < n; i++)
{
if (d[i][i] < 0)
{
cl = true;
break;
}
}
}
// 最小コストを求める
ll get_cost(ll from, ll to)
{
return d[from][to];
}
// 最短経路を求める
vector<ll> get_path(ll from, ll to)
{
if (d[from][to] == INF)
return {};
vector<ll> path;
for (ll at = from; at != to; at = next[at][to])
{
if (at == -1)
return {};
path.push_back(at);
}
path.push_back(to);
return path;
}
// 到達可能か調べる
bool cango(ll from, ll to)
{
return d[from][to] != INF;
}
// 負の閉路の有無を調べる
bool closed()
{
return cl;
}
};
// String.
struct Suffix_array
{
vector<ll> sa, rank, tmp;
ll n;
string base;
// suffix_arrayを構築
Suffix_array(const string s)
{
n = s.size();
base = s;
sa.resize(n);
rank.resize(n);
tmp.resize(n);
for (ll i = 0; i < n; i++)
{
sa[i] = i;
rank[i] = s[i];
}
for (ll k = 1; k < n; k *= 2)
{
auto compare_sa = [&](ll i, ll j)
{
if (rank[i] != rank[j])
return rank[i] < rank[j];
ll ri = (i + k < n) ? rank[i + k] : -1;
ll rj = (j + k < n) ? rank[j + k] : -1;
return ri < rj;
};
sort(sa.begin(), sa.end(), compare_sa);
tmp[sa[0]] = 0;
for (ll i = 1; i < n; i++)
{
tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
}
rank = tmp;
}
}
// 部分文字列の個数を求める
ll get_counts(string t)
{
string u = t + "彁";
ll num1, num2;
{
ll m = t.size();
ll ng = -1, ok = n;
while (ok - ng > 1)
{
ll mid = (ng + ok) / 2;
ll l = sa[mid];
if (base.substr(l, m) >= t)
{
ok = mid;
}
else
{
ng = mid;
}
}
num1 = ok;
}
{
ll m = u.size();
ll ng = -1, ok = n;
while (ok - ng > 1)
{
ll mid = (ng + ok) / 2;
ll l = sa[mid];
if (base.substr(l, m) >= u)
{
ok = mid;
}
else
{
ng = mid;
}
}
num2 = ok;
}
return num2 - num1;
}
// make lcp array
vector<ll> make_lcp()
{
vector<ll> lcp(n);
for (ll i = 0; i < n; i++)
{
rank[sa[i]] = i;
}
ll h = 0;
lcp[0] = 0;
for (ll i = 0; i < n; i++)
{
if (rank[i] == n - 1)
{
h = 0;
continue;
}
ll j = sa[rank[i] + 1];
while (i + h < n && j + h < n && base[i + h] == base[j + h])
{
h++;
}
lcp[rank[i]] = h;
if (h > 0)
{
h--;
}
}
return lcp;
}
};
// others.
class Timer
{
public:
Timer(ll ms) : duration(ms), start_time(steady_clock::now()) {}
bool isTimeOver() const
{
auto current_time = steady_clock::now();
auto elapsed = duration_cast<milliseconds>(current_time - start_time).count();
return elapsed >= duration;
}
private:
ll duration;
steady_clock::time_point start_time;
};
class FunctionalGraph
{
private:
const ll V;
ll loop_id;
vector<ll> nx;
void make_loop(const ll st, ll nw, vector<ll> &vec)
{
while (nx[nw] != st)
{
vec.push_back(nx[nw]);
visit[nx[nw]] = loop_id;
nw = nx[nw];
}
}
ll dfs(ll u, vector<ll> &vec)
{
visit[u] = -loop_id;
ll v = nx[u];
if (visit[v] == -loop_id)
{
vec.push_back(u), vec.push_back(v);
visit[u] = visit[v] = loop_id;
make_loop(u, v, vec);
loop_id++;
return 0;
}
else if (visit[v] == 0)
{
const ll res = dfs(v, vec);
if (res == 0)
return 0;
else
return visit[u] = res;
}
return visit[u] = (visit[v] > 0 ? -visit[v] : visit[v]);
}
void make_graph()
{
graph.resize(V);
for (ll i = 0; i < V; i++)
{
if (visit[i] < 0)
graph[nx[i]].push_back(i);
}
}
public:
vector<ll> visit;
vector<vector<ll>> loop, graph;
FunctionalGraph(const ll node_size)
: V(node_size), loop_id(1), nx(V, 0), visit(V, 0) {}
void add_edge(ll u, ll v)
{
nx[u] = v;
if (u == nx[u])
visit[u] = loop_id++, loop.push_back({u});
}
void solve()
{
for (ll i = 0; i < V; i++)
{
if (visit[i] == 0)
{
vector<ll> vec;
dfs(i, vec);
if (!vec.empty())
loop.push_back(move(vec));
}
}
}
};
ll op(ll a, ll b)
{
return a + b;
}
ll e()
{
return 0;
}
int main()
{
ll n, q, nowL;
cin >> n >> q >> nowL;
multiset<pair<ll, ll>> a;
multiset<ll> b;
rep(i, n)
{
ll x;
cin >> x;
b.insert(x);
a.insert({x, 0});
}
bool isNotFound = true;
vector<vector<ll>> query(q);
rep(i, q)
{
ll t;
cin >> t;
if (t == 1)
{
ll l;
cin >> l;
query[i] = {t, l};
a.insert({l, i + 1});
}
else if (t == 2)
{
ll l, r;
cin >> l >> r;
query[i] = {t, l, r};
isNotFound = false;
}
else
{
ll m;
cin >> m;
query[i] = {t, m};
}
}
if (isNotFound)
{
cout << "Not Found!" << endl;
return 0;
}
vector<vector<ll>> idx;
ll i = 0;
vector<ll> schedule;
for (auto [x, y] : a)
{
i++;
idx.push_back({y, i, x});
schedule.push_back(x);
}
reverse(all(idx));
vector<ll> segArr(idx.size(), 0);
while (true)
{
if (idx.size() == 0)
{
break;
}
if (idx.back()[0] != 0)
{
break;
}
segArr[idx.back()[1] - 1] = idx.back()[2];
idx.pop_back();
}
segtree<ll, op, e> seg(segArr);
rep(i, q)
{
if (query[i][0] == 1)
{
auto x = idx.back();
idx.pop_back();
seg.set(x[1] - 1, x[2]);
b.insert(x[2]);
}
else if (query[i][0] == 2)
{
ll l = query[i][1];
ll r = query[i][2];
ll left = lower_bound(all(schedule), l) - schedule.begin();
ll right = upper_bound(all(schedule), r) - schedule.begin();
auto l2 = b.lower_bound(l);
auto r2 = b.upper_bound(r);
cout << distance(l2, r2) << " " << seg.prod(left, right) << endl;
}
else
{
nowL = query[i][1];
}
}
return 0;
}