| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1071656 |
2024-08-23T09:44:37 Z |
vjudge1 |
Addk (eJOI21_addk) |
C++17 |
|
40 ms |
4956 KB |
//#include <bits/stdc++.h>
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;
using ll = long long;
#define int long long
const int N = 2e5 + 7;
const int M = 1e16 + 7;
struct custom_hash { //unordered_map<long long, int, custom_hash> safe_map; gp_hash_table<long long, int, custom_hash> safe_hash_table;
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
int binpow(int a, int n, int m) {
int res = 1;
while (n) {
if (n & 1) res = res * a % m;
a = a * a % m;
n >>= 1;
}
return res;
}
/*inline void factorials(int n) {
f[0] = 1;
for(int i = 1; i <= n; i++) {
f[i] = (f[i - 1] * i) % M;
}
invf[n] = binpow(f[n], M - 2, M);
for(int i = n - 1; i >= 0; i--) {
invf[i] = (invf[i + 1] * (i + 1)) % M;
}
}
inline int cnk(int n, int k) {
if(k > n) {
return 0;
}
return (((f[n] * invf[n - k]) % M) * invf[k]) % M;
} */
int a[N], t[N * 4];
void build(int v, int tl, int tr) {
if(tl == tr) {
t[v] = a[tl];
return;
}
int tm = (tl + tr) / 2;
build(v * 2, tl, tm);
build(v * 2 + 1, tm + 1, tr);
t[v] = t[v * 2] + t[v * 2 + 1];
}
void upd(int v, int tl, int tr, int pos, int val) {
if(tl == tr) {
t[v] = val;
a[tl] = val;
return;
}
int tm = (tl + tr) / 2;
if(pos <= tm) {
upd(v * 2, tl, tm, pos, val);
} else {
upd(v * 2 + 1, tm + 1, tr, pos, val);
}
t[v] = t[v * 2] + t[v * 2 + 1];
}
int get(int v, int tl, int tr, int l, int r) {
if(tl > r || tr < l || l > r) return 0;
if(l <= tl and tr <= r) {
return t[v];
}
int tm = (tl + tr) / 2;
return get(v * 2, tl, tm, l, r) + get(v * 2 + 1, tm + 1, tr, l, r);
}
inline void Solve() {
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
build(1, 1, n);
int q;
cin >> q;
for(int i = 1; i <= q; i++) {
int t;
cin >> t;
if(t == 2) {
int l, r, m, nw = 1;
cin >> l >> r >> m;
int c = 0;
if(m + m - 1 <= r) c = get(1, 1, n, l + m - 1, r - m + 1) * m;
//cout << c << ' ';
if(m + m - 1 <= r) {
for(int j = l; j <= l + m - 2; j++) {
c += a[j] * nw;
nw++;
}
nw = m - 1;
for(int j = r - m + 2; j <= r; j++) {
c += a[j] * nw;
nw--;
}
}
cout << c << '\n';
} else {
vector<int> v, pos;
int x;
cin >> x;
/*pos.push_back(x);
for(int i = 1; i < k; i++) {
int y;
cin >> y;
v.push_back(a[y]);
pos.push_back(y);
}
v.push_back(a[x]);
for(int i = 0; i < k; i++) {
upd(1, 1, n, pos[i], v[i]);
}*/
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
//cin >> t;
//cout << '\n' << '\n';
while(t--) {
Solve();
}
return 0;
}
/*
Special cases n = 1 or just 1?
u r using unsigned long long which can't carry negative values?
what if u r doing the same thing n times, it may cause the TL
make sure that the size of your massives, vectors are enough
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
4860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
4956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
