oj.uz

Submission #427248

# Submission time Handle Problem Language Result Execution time Memory
427248 2021-06-14T13:46:55 Z model_code Posters on the wall (CPSPC17_posters) C++17
100 / 100
 2230 ms 410388 KB 
#include <bits/stdc++.h>
using namespace std;

#define inf 1023456789
#define linf 1023456789123456789ll
#define pii pair<int,int>
#define pipii pair<int, pii >
#define pll pair<long long,long long>
#define vint vector<int>
#define vvint vector<vint >
#define ll long long
#define pdd pair<double, double>

#define DEBUG
#ifdef DEBUG
#define db(x) cerr << #x << " = " << x << endl
#else
#define db(x)
#endif

struct node
{
	int from, to;
	ll value;
	ll lazy;
	node *left, *right;
	bool am_leaf;
	
	node(int f, int t, ll v, node *l = NULL, node *r = NULL, ll laz = 0) : from(f), to(t), value(v), left(l), right(r), lazy(laz)
	{
		am_leaf = left == NULL;
	}
	
	ll get(int a, int b)
	{
		if(b <= from || a >= to) return 0;
		if(a <= from && b >= to) return value;
		ll length = min(b, to) - max(a, from);
		if(am_leaf) return value/(to-from) * length;
		return left->get(a, b) + right->get(a,b) + lazy * length;
	}
	
	node *add(int a, int b, ll val)
	{
		if(b <= from || a >= to) return this;
		if(a <= from && b >= to)
		{
			return new node(from, to, value+val*(to-from), left, right, lazy+val);
		}
		node *l = left->add(a, b, val);
		node *r = right->add(a, b, val);
		return new node(from, to, l->value+r->value+lazy*(to-from) , l, r, lazy);
	}
};

node *segtree(vector<int>& coors, int a, int b) //[]
{
	if(b - a == 1)
	{
		return new node(coors[a], coors[b], 0);
	}
	int mid = (a+b)/2;
	node *left = segtree(coors, a, mid);
	node *right = segtree(coors, mid, b);
	return new node(coors[a], coors[b], 0, left, right);
}

map<int, node*> current, cumulative;

ll sum_before(int x, int y1, int y2)
{
	node *cur_seg = current.lower_bound(x)->second;
	node *cum_seg = cumulative.lower_bound(x)->second;
	return cum_seg->get(y1, y2) + cur_seg->get(y1, y2)*x;
}

int main()
{
	int r, c, n, q;
	ll mod;
	scanf("%d %d %d %d %lld", &r, &c, &n, &q, &mod);
	vector<int> x1(n), y1(n), x2(n), y2(n);
	vector<pair<int, pii > > event;
	set<int> ys;
	int maxx = 0;
	for(int i=0; i<n; i++)
	{
		scanf("%d %d %d %d", &x1[i], &y1[i], &x2[i], &y2[i]);
		if(x1[i] > x2[i])swap(x1[i], x2[i]);
		if(y1[i] > y2[i])swap(y1[i], y2[i]);
		ys.insert(y1[i]);
		ys.insert(y2[i]);
		current[x1[i]] = NULL;
		current[x2[i]] = NULL;
		cumulative[x1[i]] = NULL;
		cumulative[x2[i]] = NULL;
		maxx = max(maxx, x2[i]);
		event.push_back(pipii(x1[i], pii(i, 1)));
		event.push_back(pipii(x2[i], pii(i, -1)));
	}
	vector<int> ysvec;
	for(set<int>::iterator it = ys.begin(); it != ys.end(); it++)
	{
		ysvec.push_back(*it);
	}
	node *ccur = segtree(ysvec, 0, ysvec.size()-1), *ccum = segtree(ysvec, 0, ysvec.size()-1);
	sort(event.begin(), event.end());
	for(int i=0; i<event.size(); i++)
	{
		int x = event[i].first, id = event[i].second.first, type = event[i].second.second;
		if(current[x] == NULL)
		{
			current[x] = ccur;
			cumulative[x] = ccum;
		}
		ccur = ccur->add(y1[id], y2[id], type);
		if(type == 1)
		{
			ccum = ccum->add(y1[id], y2[id], -x);
		}
		else
		{
			ccum = ccum->add(y1[id], y2[id], x);
		}
	}
	
	//queries incoming, brace yourselves
	ll l = 0;
	for(int i=0; i<q; i++)
	{
		int x1, y1, x2, y2;
		ll v;
		scanf("%d %d %d %d %lld", &x1, &y1, &x2, &y2, &v);
		x1 = (x1+(l%mod)*v)%mod;
		x2 = (x2+(l%mod)*v)%mod;
		y1 = (y1+(l%mod)*v)%mod;
		y2 = (y2+(l%mod)*v)%mod;
		if(x1 > x2)swap(x1, x2);
		if(y1 > y2)swap(y1, y2);
		x2 = min(x2, maxx);
		x1 = min(x1, maxx);
		l = sum_before(x2, y1, y2) - sum_before(x1, y1, y2);
		printf("%lld\n", l);
	}
	return 0;
}

Compilation message

Main.cpp: In constructor 'node::node(int, int, long long int, node*, node*, long long int)':
Main.cpp:26:15: warning: 'node::right' will be initialized after [-Wreorder]
   26 |  node *left, *right;
      |               ^~~~~
Main.cpp:25:5: warning:   'long long int node::lazy' [-Wreorder]
   25 |  ll lazy;
      |     ^~~~
Main.cpp:29:2: warning:   when initialized here [-Wreorder]
   29 |  node(int f, int t, ll v, node *l = NULL, node *r = NULL, ll laz = 0) : from(f), to(t), value(v), left(l), right(r), lazy(laz)
      |  ^~~~
Main.cpp: In function 'int main()':
Main.cpp:108:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |  for(int i=0; i<event.size(); i++)
      |               ~^~~~~~~~~~~~~
Main.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  scanf("%d %d %d %d %lld", &r, &c, &n, &q, &mod);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |   scanf("%d %d %d %d", &x1[i], &y1[i], &x2[i], &y2[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:133:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |   scanf("%d %d %d %d %lld", &x1, &y1, &x2, &y2, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1612 KB Output is correct
2 Correct 4 ms 1864 KB Output is correct
3 Correct 4 ms 1868 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1612 KB Output is correct
2 Correct 4 ms 1864 KB Output is correct
3 Correct 4 ms 1868 KB Output is correct
4 Correct 70 ms 23252 KB Output is correct
5 Correct 64 ms 19648 KB Output is correct
6 Correct 87 ms 23548 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1612 KB Output is correct
2 Correct 4 ms 1864 KB Output is correct
3 Correct 4 ms 1868 KB Output is correct
4 Correct 70 ms 23252 KB Output is correct
5 Correct 64 ms 19648 KB Output is correct
6 Correct 87 ms 23548 KB Output is correct
7 Correct 592 ms 242852 KB Output is correct
8 Correct 2037 ms 380652 KB Output is correct
9 Correct 1131 ms 398020 KB Output is correct
10 Correct 2029 ms 357460 KB Output is correct
11 Correct 1577 ms 243104 KB Output is correct
12 Correct 1800 ms 389500 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1612 KB Output is correct
2 Correct 4 ms 1864 KB Output is correct
3 Correct 4 ms 1868 KB Output is correct
4 Correct 70 ms 23252 KB Output is correct
5 Correct 64 ms 19648 KB Output is correct
6 Correct 87 ms 23548 KB Output is correct
7 Correct 738 ms 233200 KB Output is correct
8 Correct 2211 ms 376392 KB Output is correct
9 Correct 1291 ms 398360 KB Output is correct
10 Correct 2013 ms 354256 KB Output is correct
11 Correct 1458 ms 243564 KB Output is correct
12 Correct 1457 ms 384528 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1612 KB Output is correct
2 Correct 4 ms 1864 KB Output is correct
3 Correct 4 ms 1868 KB Output is correct
4 Correct 70 ms 23252 KB Output is correct
5 Correct 64 ms 19648 KB Output is correct
6 Correct 87 ms 23548 KB Output is correct
7 Correct 592 ms 242852 KB Output is correct
8 Correct 2037 ms 380652 KB Output is correct
9 Correct 1131 ms 398020 KB Output is correct
10 Correct 2029 ms 357460 KB Output is correct
11 Correct 1577 ms 243104 KB Output is correct
12 Correct 1800 ms 389500 KB Output is correct
13 Correct 738 ms 233200 KB Output is correct
14 Correct 2211 ms 376392 KB Output is correct
15 Correct 1291 ms 398360 KB Output is correct
16 Correct 2013 ms 354256 KB Output is correct
17 Correct 1458 ms 243564 KB Output is correct
18 Correct 1457 ms 384528 KB Output is correct
19 Correct 970 ms 410388 KB Output is correct
20 Correct 2024 ms 396336 KB Output is correct
21 Correct 1211 ms 398404 KB Output is correct
22 Correct 1967 ms 371564 KB Output is correct
23 Correct 1390 ms 249584 KB Output is correct
24 Correct 1653 ms 404380 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 214892 KB Output is correct
2 Correct 2008 ms 353432 KB Output is correct
3 Correct 1028 ms 398224 KB Output is correct
4 Correct 1801 ms 336008 KB Output is correct
5 Correct 1146 ms 236152 KB Output is correct
6 Correct 1446 ms 363768 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 214892 KB Output is correct
2 Correct 2008 ms 353432 KB Output is correct
3 Correct 1028 ms 398224 KB Output is correct
4 Correct 1801 ms 336008 KB Output is correct
5 Correct 1146 ms 236152 KB Output is correct
6 Correct 1446 ms 363768 KB Output is correct
7 Correct 1006 ms 410020 KB Output is correct
8 Correct 2230 ms 396404 KB Output is correct
9 Correct 1321 ms 398388 KB Output is correct
10 Correct 2009 ms 371680 KB Output is correct
11 Correct 1320 ms 249292 KB Output is correct
12 Correct 1524 ms 404004 KB Output is correct