結果
問題 | No.2395 区間二次変換一点取得 |
ユーザー |
![]() |
提出日時 | 2023-07-28 22:46:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 70 ms / 2,000 ms |
コード長 | 1,075 bytes |
コンパイル時間 | 863 ms |
コンパイル使用メモリ | 84,136 KB |
実行使用メモリ | 6,912 KB |
最終ジャッジ日時 | 2024-10-06 20:23:39 |
合計ジャッジ時間 | 3,029 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <iostream>#include <string>#include <set>#include <map>#include <vector>#include <queue>#define ll long long#define db doubleusing namespace std;const ll N = 1e5 + 100;ll tt,tr[N],n,md,q;struct answer{ll x,y,z;void prt() {printf("%lld %lld %lld\n",x,y,z);}}ans[N];ll lwb(ll p) {return (p & (-p));}void add(ll p,ll k) {while(p <= n) {tr[p] += k;p += lwb(p);}}ll sum(ll p) {ll res = 0;while(p > 0) {res += tr[p];p -= lwb(p);}return res;}void solve() {scanf("%lld%lld%lld",&n,&md,&q);ans[0].x = ans[0].y = ans[0].z = (1 % md);for (ll i = 1;i <= q;i++) {ans[i] = ans[i - 1];ans[i].x = (ans[i].x + 1) % md;ans[i].y = (3 * ans[i].y + ans[i].x * ans[i].z * 2) % md;ans[i].z = (3 * ans[i].z) % md;}memset(tr,0,sizeof(tr));for (ll i = 1;i <= q;i++) {ll l,m,r;scanf("%lld%lld%lld",&l,&m,&r);add(l,1);add(r + 1,-1);ans[sum(m)].prt();}}int main() {tt = 1;while(tt) {solve();tt--;}return 0;}