結果

問題 No.1000 Point Add and Array Add
ユーザー LayCurse
提出日時 2020-02-28 21:33:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 65 ms / 2,000 ms
コード長 4,596 bytes
コンパイル時間 2,538 ms
コンパイル使用メモリ 211,852 KB
最終ジャッジ日時 2025-01-09 02:37:14
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
void *wmem;
char memarr[96000000];
template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
(*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
(*arr)=(T*)(*mem);
(*mem)=((*arr)+x);
}
inline void rd(int &x){
int k;
int m=0;
x=0;
for(;;){
k = getchar_unlocked();
if(k=='-'){
m=1;
break;
}
if('0'<=k&&k<='9'){
x=k-'0';
break;
}
}
for(;;){
k = getchar_unlocked();
if(k<'0'||k>'9'){
break;
}
x=x*10+k-'0';
}
if(m){
x=-x;
}
}
inline void rd(char &c){
int i;
for(;;){
i = getchar_unlocked();
if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
break;
}
}
c = i;
}
inline int rd(char c[]){
int i;
int sz = 0;
for(;;){
i = getchar_unlocked();
if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
break;
}
}
c[sz++] = i;
for(;;){
i = getchar_unlocked();
if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
break;
}
c[sz++] = i;
}
c[sz]='\0';
return sz;
}
inline void wt_L(char a){
putchar_unlocked(a);
}
inline void wt_L(long long x){
int s=0;
int m=0;
char f[20];
if(x<0){
m=1;
x=-x;
}
while(x){
f[s++]=x%10;
x/=10;
}
if(!s){
f[s++]=0;
}
if(m){
putchar_unlocked('-');
}
while(s--){
putchar_unlocked(f[s]+'0');
}
}
template<class T> struct fenwick{
int size;
int memory;
T *data;
void malloc(int mem);
void malloc(int mem, int fg);
void walloc(int mem, void **workMemory = &wmem);
void walloc(int mem, int fg, void **workMemory = &wmem);
void free(void);
void init(int N);
void add(int k, T val);
T get(int k);
T range(int a, int b);
int kth(T k);
}
;
int N;
int Q;
int A[200000];
int X[200000];
int Y[200000];
char C[200000];
long long res[200000];
int main(){
int i;
wmem = memarr;
fenwick<int> t;
rd(N);
rd(Q);
{
int Lj4PdHRW;
for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){
rd(A[Lj4PdHRW]);
}
}
{
int e98WHCEY;
for(e98WHCEY=(0);e98WHCEY<(Q);e98WHCEY++){
rd(C[e98WHCEY]);
rd(X[e98WHCEY]);
rd(Y[e98WHCEY]);
}
}
t.malloc(N+1,1);
for(i=(Q)-1;i>=(0);i--){
if(C[i]=='A'){
res[X[i]-1] += (long long) t.get(X[i]-1) * Y[i];
}
else{
t.add(X[i]-1, 1);
t.add(Y[i], -1);
}
}
for(i=(0);i<(N);i++){
res[i] += (long long) t.get(i) * A[i];
}
{
int KrdatlYV;
if(N==0){
putchar_unlocked('\n');
}
else{
for(KrdatlYV=(0);KrdatlYV<(N-1);KrdatlYV++){
wt_L(res[KrdatlYV]);
wt_L(' ');
}
wt_L(res[KrdatlYV]);
wt_L('\n');
}
}
return 0;
}
template<class T> void fenwick<T>::malloc(int mem){
memory = mem;
data = (T*)std::malloc(sizeof(T)*mem);
}
template<class T> void fenwick<T>::malloc(int mem, int fg){
memory = mem;
data = (T*)std::malloc(sizeof(T)*mem);
if(fg){
init(mem);
}
}
template<class T> void fenwick<T>::walloc(int mem, void **workMemory /* = &wmem*/){
memory = mem;
walloc1d(&data, mem, workMemory);
}
template<class T> void fenwick<T>::walloc(int mem, int fg, void **workMemory /* = &wmem*/){
memory = mem;
walloc1d(&data, mem, workMemory);
if(fg){
init(mem);
}
}
template<class T> void fenwick<T>::free(void){
memory = 0;
free(data);
}
template<class T> void fenwick<T>::init(int N){
size = N;
memset(data,0,sizeof(T)*N);
}
template<class T> void fenwick<T>::add(int k, T val){
while(k < size){
data[k] += val;
k |= k+1;
}
}
template<class T> T fenwick<T>::get(int k){
T res = 0;
while(k>=0){
res += data[k];
k = (k&(k+1))-1;
}
return res;
}
template<class T> T fenwick<T>::range(int a, int b){
if(b==-1){
b=size-1;
}
return get(b) - get(a-1);
}
template<class T> int fenwick<T>::kth(T k){
int i=0;
int j=size;
int c;
T v;
while(i<j){
c = (i+j)/2;
v = get(c);
if(v <= k){
i=c+1;
}
else{
j=c;
}
}
return i==size?-1:i;
}
// cLay varsion 20200227-1
// --- original code ---
// int N, Q, A[2d5], X[2d5], Y[2d5]; char C[2d5];
// ll res[2d5];
// {
// fenwick<int> t;
// rd(N,Q,A(N),(C,X,Y)(Q));
// t.malloc(N+1,1);
// rrep(i,Q){
// if(C[i]=='A'){
// res[X[i]-1] += (ll) t.get(X[i]-1) * Y[i];
// } else {
// t.add(X[i]-1, 1);
// t.add(Y[i], -1);
// }
// }
// rep(i,N) res[i] += (ll) t.get(i) * A[i];
// wt(res(N));
// }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0