Submission #754340

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
754340	2023-06-07 14:07:35	dsyz	Addk (eJOI21_addk)	C++17	100 / 100	201 ms	12616 KiB

Main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (100005)
ll N,K;
struct fenwick {
  ll fw[MAXN], fw2[MAXN];
  fenwick() {
    memset(fw,0,sizeof(fw));
    memset(fw2,0,sizeof(fw2));
  }
  void update(ll x,ll y,ll v){
    y++;
    for(ll tx = x;tx <= N;tx += tx&(-tx)) fw[tx] += v,fw2[tx] -= v * (x - 1);
    for(ll ty = y;ty <= N;ty += ty&(-ty)) fw[ty] -= v,fw2[ty] += v * (y - 1);
  }
  long long sum(long long x){
    ll ans = 0;
    for(ll tx = x;tx;tx -= tx&(-tx)){
      ans += (fw[tx] * x) + fw2[tx];
    }
    return ans;
  }
  long long range_sum(long long x,long long y){
    return sum(y) - sum(x - 1);
  }
} front, middle, back;
int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  //note that everything is 1-indexed
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 36 / 36
• Subtask 2: 56 / 56
• Subtask 3: 8 / 8