Submission #247500

# Submission time Handle Problem Language Result Execution time Memory
247500 2020-07-11T13:37:32 Z xiryss Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
114 ms 7960 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 (k == 1)
	{
		return;
	}
	if (t[v].mx < k && l >= ql && r<=qr)
	{
		t[v] = { 0,0 };
		return;
	}
	if (l == r - 1)
	{
		t[v].mx = t[v].mx / k;
		t[v].sum = t[v].sum / k;
		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:151: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:176:2: note: in expansion of macro 'sp'
  sp;
  ^~
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 6656 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 71 ms 7416 KB Output is correct
2 Correct 63 ms 7288 KB Output is correct
3 Correct 66 ms 7596 KB Output is correct
4 Correct 84 ms 7800 KB Output is correct
5 Correct 97 ms 7960 KB Output is correct
6 Correct 90 ms 7928 KB Output is correct
7 Correct 92 ms 7928 KB Output is correct
8 Correct 101 ms 7928 KB Output is correct
9 Correct 93 ms 7928 KB Output is correct
10 Correct 88 ms 7928 KB Output is correct
11 Correct 89 ms 7928 KB Output is correct
12 Correct 88 ms 7928 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 6656 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 7160 KB Output isn't correct
2 Halted 0 ms 0 KB -