| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1348459 | po_rag526 | Peru (RMI20_peru) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<typename T> struct MonoidQueue {
static T merge(T a, T b) { return a | b; } // TODO: min(a,b), max(a,b), a|b,...
static T id() { return T{}; } // TODO: (neutral) 0 for sum, INF for min, "" for string,...
struct MonoStack {
vector<pair<T, T>> st;
// O(1) amortized push
void push(const T& x) {
T cur = st.empty() ? x : merge(st.back().second, x);
st.emplace_back(x, cur);
}
void pop() { if (!st.empty()) st.pop_back(); }
T get() const { return st.empty() ? id() : st.back().second; }
T top() const { return st.back().first; } // caller guarantees !empty
bool empty() const { return st.empty(); }
size_t size() const { return st.size(); }
};
MonoStack in, out;
void push_back(const T& x) { in.push(x); }
void pop_front() {
if (out.empty()) transfer();
out.pop();
}
T front() {
if (out.empty()) transfer();
return out.top();
}
size_t size() const { return in.size() + out.size(); }
bool empty() const { return in.empty() && out.empty(); }
// O(1) aggregate (front-to-back order)
T get() const {
if (empty()) return id();
if (in.empty()) return out.get();
if (out.empty()) return in.get();
return merge(out.get(), in.get());
}
private:
void transfer() {
while (!in.empty()) {
out.push(in.top());
in.pop();
}
}
};
vector<int> v, ans;
void Main(int tc) {
int n, k; cin >> n >> k;
v.resize(n);
int x, a, b, c; cin >> x >> a >> b >> c;
v[0] = x;
for(int i = 1; i < n; ++i) v[i] = (1LL*a*v[i-1]+b)%c;
MonoidQueue<int> mq;
for (int i = 0; i < k; ++i) mq.push_back(v[i]);
ans.emplace_back(mq.get());
for(int i = k; i < n; ++i) {
mq.pop_front();
mq.push_back(v[i]);
ans.emplace_back(mq.get());
}
int res = 0;
for(auto& i : ans) res ^= i;
cout << res;
}
int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
int tc = 1;
// cin >> tc;
for(int _ = 1; _ <= tc; ++_) Main(_);
return 0;
}