답안 #320178

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
320178	2020-11-07T21:01:59 Z	arwaeystoamneg	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	761 ms	233956 KB

apple

/*
ID: awesome35
LANG: C++14
TASK: vans
*/
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
// warning: ld is rougly 2x slower than double. Proof: ld: https://oj.uz/submission/319677 double: https://oj.uz/submission/319678
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
//#define endl '\n'
#define test int testc;cin>>testc;while(testc--)
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353
const ld pi = 3.1415926535;

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void build_primes(vi& primes, int size)
{
	vi visited;
	visited.rsz(size, 0);
	FOR(i, 2, size)
	{
		if (visited[i] == 0)
		{
			primes.pb(i);
			int a = i;
			while (a < size)
			{
				visited[a] = 1;
				a += i;
			}
		}
	}
}
vector<vector<ll>> matrix_mult(vector<vector<ll>>& a, vector<vector<ll>>& b)
{
	int n = a.size();
	vector<vector<ll>> answer;
	answer.resize(n);
	for (int i = 0; i < n; i++) answer[i].resize(n, 0);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++) // calculate answer[i][j]
		{
			for (int k = 0; k < n; k++)
				answer[i][j] = (answer[i][j] + a[i][k] * b[k][j]) % inf;
		}
	}
	return answer;
}
int modInverse(int a, int m)
{
	int m0 = m;
	int y = 0, x = 1;
	if (m == 1)
		return 0;
	while (a > 1)
	{
		// q is quotient 
		int q = a / m;
		int t = m;
		// m is remainder now, process same as 
		// Euclid's algo 
		m = a % m, a = t;
		t = y;
		// Update y and x 
		y = x - q * y;
		x = t;
	}
	// Make x positive 
	if (x < 0)
		x += m0;

	return x;
}
ll power(ll x, ll y)
{
	ll k = 1LL << 60;
	ll z = 1;
	while (k != 0)
	{
		z *= z;
		z %= inf;
		if (y >= k)
		{
			z *= x;
			z %= inf;
			y -= k;
		}
		k >>= 1;
	}
	return z;
}
struct point
{
	ld x, y;
	bool operator<(const point& rhs)const
	{
		if (x == rhs.x)return y < rhs.y;
		return x < rhs.x;
	}
};
struct pt
{
	ll x, y;
	bool operator<(const pt& rhs)const
	{
		if (x == rhs.x)return y < rhs.y;
		return x < rhs.x;
	}
};
// remember that you need to take abs
long double area(point x, point y, point z)
{
	return (x.y * y.x + y.y * z.x + z.y * x.x - x.x * y.y - y.x * z.y - z.x * x.y) / 2.0;
}
bool clockwise(point x, point y, point z)
{
	return area(x, y, z) > 0;
}
// remember that you need to take abs
long double area(pt x, pt y, pt z)
{
	return (x.y * y.x + y.y * z.x + z.y * x.x - x.x * y.y - y.x * z.y - z.x * x.y) / 2.0;
}
bool clockwise(pt x, pt y, pt z)
{
	return area(x, y, z) > 0;
}
ll gcd(ll a, ll b)
{
	if (a > b)swap(a, b);
	if (a == 0)return b;
	return gcd(a, b % a);
}
int popcount(ll a)
{
	int count = 0;
	while (a)
	{
		count += (a & 1);
		a >>= 1;
	}
	return count;
}
ll choose(ll n, ll r)
{
	ll p = 1, k = 1;
	if (n - r < r)
		r = n - r;
	if (r != 0) {
		while (r) {
			p *= n;
			k *= r;
			long long m = gcd(p, k);
			p /= m;
			k /= m;
			n--;
			r--;
		}
	}
	else
		p = 1;
	return p;
}
vll prefix_hash(string& a, vll& powers, ll mod)
{
	int n = sz(a);
	vll prefix(n + 1);
	F0R(i, n)prefix[i + 1] = (prefix[i] + powers[i] * (a[i] - '1' + 1)) % mod;
	return prefix;
}
struct custom_hash {
	static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
	//the return type was size_t. But isnt that problematic?
	uint64_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};
struct custom_hash_fast {
	//the return type was size_t. But isnt that problematic?
	uint64_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		x ^= FIXED_RANDOM;
		return x ^ (x >> 16);
	}
};
const int MAX = (1 << 30) - 1;
class sum_range_tree
{
	struct node
	{
		int val;
		bool update_;
		struct node* C[2];
		node()
		{
			val = 0;
			C[0] = NULL;
			C[1] = NULL;
			update_ = 0;
		}
		node* getc(int c)
		{
			if (C[c] == NULL)
			{
				C[c] = new node;
			}
			return C[c];
		}
		void push(int l, int r)
		{
			if (update_)
			{
				val = r - l + 1;
				if (l != r)
				{
					getc(0)->update_ = 1;
					getc(1)->update_ = 1;
				}
				update_ = 0;
			}
		}
		void update(int ul, int ur, int l, int r)
		{
			push(l, r);
			if (ul > r || ur < l)return;
			if (l >= ul && r <= ur)
			{
				update_ = 1;
				push(l, r);
				return;
			}
			int mid = ((l + r < 0) ? (l + r - 1) / 2 : (l + r) / 2);
			if (ul > mid)
			{
				getc(1)->update(ul, ur, mid + 1, r);
				getc(0)->push(l, mid);
			}
			else if (ur <= mid)
			{
				getc(0)->update(ul, ur, l, mid);
				getc(1)->push(mid + 1, r);
			}
			else
			{
				getc(0)->update(ul, ur, l, mid);
				getc(1)->update(ul, ur, mid + 1, r);				
			}
			val = (C[0] ? C[0]->val : 0) + (C[1] ? C[1]->val : 0);
		}
		// sl and sr are tl and tr
		int query(int ql, int qr, int sl, int sr)
		{
			push(sl, sr);
			if (sl >= ql && sr <= qr)
				return val;
			else if (sr<ql || sl>qr)
				return 0;
			int mid = ((sl + sr < 0) ? (sl + sr - 1) / 2 : (sl + sr) / 2);
			if (ql > mid)return getc(1)->query(ql, qr, mid + 1, sr);
			else if (qr <= mid)return getc(0)->query(ql, qr, sl, mid);
			else return (C[0] ? C[0]->query(ql, qr, sl, mid) : 0) + (C[1] ? C[1]->query(ql, qr, mid + 1, sr) : 0);
		}
	};
	node* top;
public:void build()
{
	top = new node;
}
public:void update(int tl, int tr)
{
	top->update(tl, tr, 0, MAX);
}
public:int query(int l, int r)
{
	return top->query(l, r, 0, MAX);
}
};
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test3")
			freopen((s + ".out").c_str(), "w", stdout);
	}
}
int main()
{
	setIO("");
	sum_range_tree sum;
	sum.build();
	int C = 0;
	test
	{
		int a,b;
	cin >> a;
	if (a == 1)
	{
		cin >> a >> b;
		a += C;
		b += C;
		C = sum.query(a, b);
		cout << C << endl;
	}
	else
	{
		cin >> a >> b;
		a += C;
		b += C;
		sum.update(a, b);
	}
	}
}

Compilation message

apple.cpp: In function 'void setIO(std::string)':
apple.cpp:320:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  320 |   freopen((s + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:322:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  322 |    freopen((s + ".out").c_str(), "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	7 ms	512 KB	Output is correct
4	Correct	28 ms	5468 KB	Output is correct
5	Correct	35 ms	6500 KB	Output is correct
6	Correct	33 ms	6464 KB	Output is correct
7	Correct	37 ms	6600 KB	Output is correct
8	Correct	246 ms	47836 KB	Output is correct
9	Correct	485 ms	79572 KB	Output is correct
10	Correct	549 ms	91224 KB	Output is correct
11	Correct	528 ms	98732 KB	Output is correct
12	Correct	534 ms	102056 KB	Output is correct
13	Correct	497 ms	122824 KB	Output is correct
14	Correct	517 ms	124388 KB	Output is correct
15	Correct	743 ms	227096 KB	Output is correct
16	Correct	751 ms	228580 KB	Output is correct
17	Correct	501 ms	128644 KB	Output is correct
18	Correct	503 ms	128612 KB	Output is correct
19	Correct	746 ms	233700 KB	Output is correct
20	Correct	761 ms	233956 KB	Output is correct