| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 924610 |
2024-02-09T09:38:13 Z |
pan |
Addk (eJOI21_addk) |
C++17 |
|
812 ms |
40224 KB |
#include <bits/stdc++.h>
//#include "bits_stdc++.h"
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
ll n, k, q, t, l, r, m;
vector<ll> arr, change, newval;
struct node{
ll s, e, m; //range is [s,e], m is the middle point
ll val; //sum of [s,e]
node *l, *r; //create two children l and r, where l is [s,m] and [m+1,e]
node (ll S, ll E){ //constructor called node
s = S, e = E, m = (s+e)/2;
val = 0; //initially all values are 0
l= r= nullptr;
}
void create()
{
if(l==nullptr && s != e){ //node is not yet a leaf, so create two children
l = new node(s, m); //create left child
r = new node(m+1, e); //create right child
}
}
void update(ll X, ll V){ //change the X-th element to be value V
if(s == e) val = V; //node is leaf, update value
else{ //go down to find the leaf
create();
if(X <= m) { l->update(X, V);} //X is in the left child
else {r->update(X, V);} //X is in the right child
val = l->val + r->val; //update the range sum
}
}
ll query(ll S, ll E){
if(s == S && e == E) {return val;}//case 1
create();
if(E <= m) return l->query(S, E); //case 2, recurse to left child
else if(S >= m+1) return r->query(S, E); //case 3, recurse to right child
else return l->query(S, m) + r->query(m+1, E); //case 4, split the query range, recurse to both childs
}
} *root1, *root2, *root3;
int main()
{
input(n); input(k);
arr.resize(n+1);
change.resize(k);
newval.resize(k);
root1 = new node(1, n);
root2 = new node(1, n);
root3 = new node(1, n);
for (ll i=1; i<=n; ++i)
{
input(arr[i]);
root1->update(i, arr[i]);
root2->update(i, arr[i]*i);
root3->update(i, arr[i]*(n-i+1));
}
input(q);
while (q--)
{
input(t);
if (t==1)
{
for (ll i=0; i<k; ++i) input(change[i]);
if (k==1) {continue;}
for (ll i=0; i<k; ++i)
{
if (i==k-1) newval[i] = arr[change[0]];
else newval[i] = arr[change[i+1]];
}
for (ll i=0; i<k; ++i)
{
root1->update(change[i], newval[i]);
root2->update(change[i], newval[i]*change[i]);
root3->update(change[i], newval[i]*(n-change[i]+1));
arr[change[i]] = newval[i];
}
}
else
{
input(l); input(r); input(m);
ll siz = r-l+1;
if (siz<m) {print(0LL, '\n');}
else if (m==1)
{
print(root1->query(l, r), '\n');
}
else if (m==2)
{
ll ans = arr[l] + arr[r];
if (siz>2) ans+=2*root1->query(l+1, r-1);
print(ans, '\n');
}
else
{
ll ans = 0;
ll maxx = min(siz-m+1, m);
ans += root2->query(l, l+maxx-1) - (l-1)*root1->query(l, l+maxx-1);
ans+=root3->query(r-maxx+1, r) - (n-r)*root1->query(r-maxx+1, r);
if ((r-maxx+1)-(l+maxx-1)>1) ans+=root1->query(l+maxx, r-maxx)*maxx;
print(ans, '\n');
}
}
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input(x) scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
Main.cpp:67:2: note: in expansion of macro 'input'
67 | input(n); input(k);
| ^~~~~
Main.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input(x) scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
Main.cpp:67:12: note: in expansion of macro 'input'
67 | input(n); input(k);
| ^~~~~
Main.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input(x) scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
Main.cpp:76:3: note: in expansion of macro 'input'
76 | input(arr[i]);
| ^~~~~
Main.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input(x) scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
Main.cpp:81:2: note: in expansion of macro 'input'
81 | input(q);
| ^~~~~
Main.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input(x) scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
Main.cpp:84:3: note: in expansion of macro 'input'
84 | input(t);
| ^~~~~
Main.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input(x) scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
Main.cpp:88:27: note: in expansion of macro 'input'
88 | for (ll i=0; i<k; ++i) input(change[i]);
| ^~~~~
Main.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input(x) scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
Main.cpp:105:4: note: in expansion of macro 'input'
105 | input(l); input(r); input(m);
| ^~~~~
Main.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input(x) scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
Main.cpp:105:14: note: in expansion of macro 'input'
105 | input(l); input(r); input(m);
| ^~~~~
Main.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input(x) scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
Main.cpp:105:24: note: in expansion of macro 'input'
105 | input(l); input(r); input(m);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
8372 KB |
Output is correct |
| 2 |
Correct |
72 ms |
12116 KB |
Output is correct |
| 3 |
Correct |
109 ms |
16312 KB |
Output is correct |
| 4 |
Correct |
234 ms |
28296 KB |
Output is correct |
| 5 |
Correct |
370 ms |
40136 KB |
Output is correct |
| 6 |
Correct |
355 ms |
40076 KB |
Output is correct |
| 7 |
Correct |
323 ms |
40020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
264 ms |
20332 KB |
Output is correct |
| 2 |
Correct |
351 ms |
32180 KB |
Output is correct |
| 3 |
Correct |
812 ms |
39464 KB |
Output is correct |
| 4 |
Correct |
447 ms |
40224 KB |
Output is correct |
