oj.uz

Submission #247504

# Submission time Handle Problem Language Result Execution time Memory
247504 2020-07-11T13:43:12 Z xiryss Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 334 ms 7672 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;
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:148: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:173: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 12 ms 6656 KB Output is correct
5 Correct 13 ms 6656 KB Output is correct
6 Correct 12 ms 6656 KB Output is correct
7 Correct 12 ms 6656 KB Output is correct
8 Correct 12 ms 6656 KB Output is correct
9 Correct 14 ms 6656 KB Output is correct
10 Correct 13 ms 6776 KB Output is correct
11 Correct 13 ms 6784 KB Output is correct
12 Correct 13 ms 6656 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 7288 KB Output is correct
2 Correct 64 ms 7160 KB Output is correct
3 Correct 74 ms 7288 KB Output is correct
4 Correct 85 ms 7544 KB Output is correct
5 Correct 96 ms 7544 KB Output is correct
6 Correct 98 ms 7544 KB Output is correct
7 Correct 99 ms 7544 KB Output is correct
8 Correct 98 ms 7672 KB Output is correct
9 Correct 91 ms 7544 KB Output is correct
10 Correct 96 ms 7544 KB Output is correct
11 Correct 100 ms 7544 KB Output is correct
12 Correct 107 ms 7544 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6656 KB Output is correct
2 Correct 38 ms 6912 KB Output is correct
3 Correct 35 ms 7032 KB Output is correct
4 Correct 65 ms 6904 KB Output is correct
5 Correct 95 ms 7168 KB Output is correct
6 Correct 93 ms 7416 KB Output is correct
7 Correct 86 ms 7364 KB Output is correct
8 Correct 92 ms 7168 KB Output is correct
9 Correct 86 ms 7168 KB Output is correct
10 Correct 91 ms 7160 KB Output is correct
11 Correct 82 ms 7168 KB Output is correct
12 Correct 84 ms 7160 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 7032 KB Output is correct
2 Correct 124 ms 7288 KB Output is correct
3 Correct 136 ms 7160 KB Output is correct
4 Correct 145 ms 7160 KB Output is correct
5 Correct 180 ms 7416 KB Output is correct
6 Correct 207 ms 7416 KB Output is correct
7 Correct 176 ms 7544 KB Output is correct
8 Correct 236 ms 7472 KB Output is correct
9 Correct 224 ms 7416 KB Output is correct
10 Correct 249 ms 7416 KB Output is correct
11 Correct 184 ms 7416 KB Output is correct
12 Correct 334 ms 7544 KB Output is correct