結果
問題 | No.925 紲星 Extra |
ユーザー |
![]() |
提出日時 | 2024-12-07 00:12:51 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,150 bytes |
コンパイル時間 | 5,120 ms |
コンパイル使用メモリ | 269,812 KB |
実行使用メモリ | 11,136 KB |
最終ジャッジ日時 | 2024-12-07 00:13:54 |
合計ジャッジ時間 | 60,472 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | RE * 15 TLE * 4 |
ソースコード
#include <stdio.h>#include <atcoder/all>#include <bits/stdc++.h>using namespace std;using namespace atcoder;using mint = modint998244353;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf32 1000000001#define Inf64 1000000000000000000LLint B = 1<<4;void setting(vector<long long> &a,vector<vector<long long>> &vs,vector<vector<long long>> &sums,int ind){vs[ind].clear();sums[ind].clear();for(int i=B*ind;i<min((int)a.size(),B*(ind+1));i++){vs[ind].push_back(a[i]);}sort(vs.begin(),vs.end());sums[ind].push_back(0);for(int i=0;i<vs[ind].size();i++){sums[ind].push_back(sums[ind][i]+vs[ind][i]);}}int main(){int n,q;cin>>n>>q;vector<long long> a(n);rep(i,n){cin>>a[i];}vector<vector<long long>> vs((n+B-1)/B,vector<long long>());vector<vector<long long>> sums((n+B-1)/B,vector<long long>());for(int i=0;i<n;i+=B){setting(a,vs,sums,i/B);}long long last = 0;rep(_,q){long long t,x,y;cin>>t>>x>>y;if(t==1){x ^= last & ((1<<16)-1);y ^= last & ((1LL<<40)-1);x--;a[x] = y;setting(a,vs,sums,x/B);}else{x ^= last & ((1<<16)-1);y ^= last & ((1<<16)-1);long long temp = last;if(x>y){swap(x,y);}x--;long long ok = -1,ng = 1LL<<41;while(ng-ok>1LL){long long mid = (ok+ng)/2;long long l = x,r = y;int cnt = 0;while(l<r){if(l%B!=0 || l+B>=r){if(a[l]<=mid)cnt++;l++;}else{cnt += distance(vs[l/B].begin(),upper_bound(vs[l/B].begin(),vs[l/B].end(),mid));l += B;}}if(cnt <= (y-x)/2)ok = mid;else ng = mid;}ok++;last = 0;long long l = x,r = y;while(l<r){if(l%B!=0 || l+B>=r){if(a[l]<=ok){last += ok-a[l];}else last += a[l]-ok;l++;}else{int ind = l/B;int num = distance(vs[ind].begin(),upper_bound(vs[ind].begin(),vs[ind].end(),ok));last -= sums[ind][num];last += sums[ind].back() - sums[ind][num];last += ok * num;last -= (long long)vs[ind].size() * ok;l += B;}}cout<<last<<endl;last ^= temp;}}return 0;}