oj.uz

Submission #247503

# Submission time Handle Problem Language Result Execution time Memory
247503 2020-07-11T13:42:53 Z xiryss Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 317 ms 10360 KB 
//#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
/*#pragma GCC optimize("section-anchors")
#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
#pragma GCC optimize("vpt")
#pragma GCC optimize("rename-registers")
#pragma GCC optimize("move-loop-invariants")
#pragma GCC optimize("unswitch-loops")
#pragma GCC optimize("function-sections")
#pragma GCC optimize("data-sections")
#pragma GCC optimize("branch-target-load-optimize")
#pragma GCC optimize("branch-target-load-optimize2")
#pragma GCC optimize("btr-bb-exclusive")*/
//#pragma comment(linker, "/STACK:367077216")
#define _CRT_SECURE_NO_WARNINGS
#include <chrono>
#include <set>
#include <map>
#include <deque>
#include <string>
#include <cstdint>
#include <cmath>
#include <queue>
#include <cassert>
#include <random>
#include <bitset>
#include <iomanip>
#include <numeric>
#include <time.h>//////////////
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
//++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
//#define endl '\n'
#define mp make_pair
#define pbc push_back
#define pob pop_back()
#define empb emplace_back
#define queuel queue<long long>
#define sqr(a) ((a) * (a))
#define sqrl(a) (ll(a)*ll(a))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pin(p) cin >> p.first >> p.second;
#define uniq(a) sort(all(a));(a).resize(unique(all(a)) - a.begin());
#define rev(v) reverse(v.begin(), v.end());
#define sout(s, c) for (auto i : s) cout << i << c;
#define pout(p) cout << p.first << " " << p.second;
#define er(v, l, r) erase(v.begin() + l, v.begin() + r);
#define vin(v) for (ll i = 0; i < v.size(); ++i) cin >> v[i];
#define vout(v, c) for (int i = 0; i < v.size(); ++i) cout << v[i] << c;
#define pushi(v, a) for (int i = 0; i < a.size(); ++i) v.push_back(a[i]);
#define fastio() ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); srand(time(NULL))
#define dab(v) for(auto i:v)cout<<i<<' ';
#define sp system("pause")
//++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
using namespace std;
//++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
//++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
mt19937 rnd(time(0) + 228 + 'k' + 'e' + 'k' + 'e' + 'r' + 'o' + 'f' + 'e' + 'y');
const ld EPS = 1e-5;//(cos,-sin), (sin, cos)
bool checkprime(int x)
{
	for (int i = 2; i * i <= x; ++i) if (x % i == 0) return 0;
	return 1;
}
const ld PI = acos(-1);
const int MOD7 = 1000000007;
const int MOD9 = 1000000009;
const ll INF = 1e18;
int mod = MOD9;
const int inf = 1e9;
const int MAXN = 1e5 + 2;
#define int ll
int n, q, k;
struct node
{
	int mx;
	ll sum;
	node()
	{
		mx = 0, sum = 0;
	}
	node(int a, ll b)
	{
		mx = a, sum = b;
	}
};
vector<int> a;
node t[4 * MAXN];

void upd(int v, int l, int r, int ql, int qr)
{
	if (l >= qr || ql >= r) return;
	if (l == r - 1)
	{
		t[v].mx = t[v].mx / k;
		t[v].sum = t[v].sum / k;
		return;
	}
	if (!t[v].mx) return;
	if (k == 1)
	{
		return;
	}
	
	upd(2 * v + 1, l, (l + r) / 2, ql, qr);
	upd(2 * v + 2, (l + r) / 2, r, ql, qr);
	t[v].mx = max(t[2 * v + 1].mx, t[2 * v + 2].mx);
	t[v].sum = t[2 * v + 1].sum + t[2 * v + 2].sum;
}
void place(int v, int l, int r, int ql, int qr, int x)
{
	if (l >= qr || ql >= r) return;
	if (l >= ql && r <= qr)
	{
		t[v] = { x,x };
		return;
	}
	place(2 * v + 1, l, (l + r) / 2, ql, qr, x);
	place(2 * v + 2, (l + r) / 2, r, ql, qr, x);
	t[v].mx = max(t[2 * v + 1].mx, t[2 * v + 2].mx);
	t[v].sum = t[2 * v + 1].sum + t[2 * v + 2].sum;
}
ll get(int v, int l, int r, int ql, int qr)
{
	if (l >= qr || ql >= r) return 0;
	if (l >= ql && r <= qr) return t[v].sum;
	ll g1 = get(2 * v + 1, l, (l + r) / 2, ql, qr);
	ll g2 = get(2 * v + 2, (l + r) / 2, r, ql, qr);
	return g1 + g2;
}
signed main()
{
	fastio();
	cin >> n >> q >> k;
	a.resize(n);
	vin(a);
	for (int i = 0; i < n; ++i) place(0, 0, n, i, i + 1, a[i]);
	for (int i = 0; i < q; ++i)
	{
		int tp;
		cin >> tp;
		if (tp == 1)
		{
			int a, b;
			cin >> a >> b;
			place(0, 0, n, a - 1, a, b);
		}
		else if (tp == 2)
		{
			int l, r;
			cin >> l >> r;
			upd(0, 0, n, l - 1, r);
		}
		else
		{
			int l, r;
			cin >> l >> r;
			cout << get(0, 0, n, l - 1, r) << '\n';
		}
	}
	sp;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:58:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define vin(v) for (ll i = 0; i < v.size(); ++i) cin >> v[i];
                               ~~^~~~~~~~~~
sterilizing.cpp:149:2: note: in expansion of macro 'vin'
  vin(a);
  ^~~
sterilizing.cpp:63:18: warning: ignoring return value of 'int system(const char*)', declared with attribute warn_unused_result [-Wunused-result]
 #define sp system("pause")
            ~~~~~~^~~~~~~~~
sterilizing.cpp:174:2: note: in expansion of macro 'sp'
  sp;
  ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6656 KB Output is correct
2 Correct 9 ms 6656 KB Output is correct
3 Correct 9 ms 6656 KB Output is correct
4 Correct 14 ms 6656 KB Output is correct
5 Correct 13 ms 6784 KB Output is correct
6 Correct 12 ms 6784 KB Output is correct
7 Correct 16 ms 6784 KB Output is correct
8 Correct 13 ms 6784 KB Output is correct
9 Correct 12 ms 6784 KB Output is correct
10 Correct 12 ms 6784 KB Output is correct
11 Correct 12 ms 6784 KB Output is correct
12 Correct 12 ms 6784 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 7520 KB Output is correct
2 Correct 65 ms 7288 KB Output is correct
3 Correct 67 ms 7544 KB Output is correct
4 Correct 83 ms 7800 KB Output is correct
5 Correct 102 ms 7932 KB Output is correct
6 Correct 95 ms 7928 KB Output is correct
7 Correct 96 ms 7928 KB Output is correct
8 Correct 99 ms 7928 KB Output is correct
9 Correct 87 ms 7928 KB Output is correct
10 Correct 91 ms 7916 KB Output is correct
11 Correct 88 ms 7928 KB Output is correct
12 Correct 91 ms 7928 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6656 KB Output is correct
2 Correct 27 ms 7296 KB Output is correct
3 Correct 47 ms 7416 KB Output is correct
4 Correct 66 ms 8056 KB Output is correct
5 Correct 93 ms 8952 KB Output is correct
6 Correct 100 ms 8952 KB Output is correct
7 Correct 98 ms 9124 KB Output is correct
8 Correct 99 ms 8952 KB Output is correct
9 Correct 89 ms 8708 KB Output is correct
10 Correct 87 ms 8824 KB Output is correct
11 Correct 87 ms 8696 KB Output is correct
12 Correct 87 ms 8824 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 7160 KB Output is correct
2 Correct 119 ms 8952 KB Output is correct
3 Correct 138 ms 8312 KB Output is correct
4 Correct 148 ms 8824 KB Output is correct
5 Correct 176 ms 10104 KB Output is correct
6 Correct 190 ms 10104 KB Output is correct
7 Correct 169 ms 10360 KB Output is correct
8 Correct 239 ms 10208 KB Output is correct
9 Correct 212 ms 9976 KB Output is correct
10 Correct 249 ms 10104 KB Output is correct
11 Correct 186 ms 9976 KB Output is correct
12 Correct 317 ms 10104 KB Output is correct