oj.uz

답안 #247499

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
247499 2020-07-11T13:35:24 Z xiryss Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 100 ms 7932 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)
	{
		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;
  ^~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 6656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 7544 KB Output is correct
2 Correct 62 ms 7288 KB Output is correct
3 Correct 63 ms 7544 KB Output is correct
4 Correct 79 ms 7800 KB Output is correct
5 Correct 92 ms 7928 KB Output is correct
6 Correct 89 ms 7928 KB Output is correct
7 Correct 100 ms 7928 KB Output is correct
8 Correct 96 ms 7928 KB Output is correct
9 Correct 92 ms 7928 KB Output is correct
10 Correct 90 ms 7928 KB Output is correct
11 Correct 87 ms 7932 KB Output is correct
12 Correct 88 ms 7928 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 6784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 58 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -