Submission #239321

#	Time	Username	Problem	Language	Result	Execution time	Memory
239321		MrRobot_28	Automobil (COCI17_automobil)	C++17	100 / 100	70 ms	8496 KiB

automobil

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int const1 = 1e9 + 7;
int power(int a, int b)
{
	if(b == 0)
	{
		return 1;
	}
	else if(b % 2 == 0)
	{
		int t = power(a, b / 2);
		return t * t % const1;
	}
	else
	{
		int t= power(a, b / 2);
		t = t * t % const1;
		return t * a % const1;
	}
}
signed main()
{
	int n, m, k;
	cin >> n >> m >> k;
	int inv2 = power(2, const1 - 2);
	int ans = n * m % const1 * (n * m % const1 + 1) % const1 * inv2 % const1;
	vector <pair <int, int> > p1, p2;
	vector <pair <int, int> > pointsx, pointsy;
	for(int i = 0; i < k; i++)
	{
		char t;
		cin >> t;
		int x, y;
		cin >> x >> y;
		if(t == 'R')
		{
			p1.push_back({x, y});
		}
		else
		{
			p2.push_back({x, y});
		}
	}
	sort(p1.begin(), p1.end());
	sort(p2.begin(), p2.end());
	for(int i = 0; i < p1.size(); i++)
	{
		for(int j = 0; j < p2.size(); j++)
		{
			pointsx.push_back({p1[i].first, p2[j].first});
			pointsy.push_back({p2[j].first, p1[i].first});
		}
	}
	sort(pointsx.begin(), pointsx.end());
	sort(pointsy.begin(), pointsy.end());
	int X = unique(pointsx.begin(), pointsx.end()) - pointsx.begin();
	int Y = unique(pointsy.begin(), pointsy.end()) - pointsy.begin();
	int iter = 0;
	for(int i = 0; i < p1.size(); i++)
	{
		int j = i;
		int p = 1;
		while(j < p1.size() && p1[j].first == p1[i].first)
		{
			p = p * p1[j].second % const1;
			j++;
		}
		int sum1 = 0;
		while(iter < X && pointsx[iter].first < p1[i].first)
		{
			iter++;
		}
		while(iter < X && pointsx[iter].first == p1[i].first)
		{
			sum1 += (pointsx[iter].first - 1) * m + pointsx[iter].second;
			sum1 %= const1;
			iter++;
		}
		sum1 %= const1;
		sum1 = ((m * (p1[i].first - 1) * 2 + m + 1) % const1) * m % const1 * inv2 % const1 - sum1;
		if(sum1 < 0)
		{
			sum1 += const1;
		}
		ans = ans - sum1;
		if(ans < 0)
		{
			ans += const1;
		}
		ans = (ans + sum1 * p) % const1;
		p1[i].second = p;
		i = j - 1;
	}
	iter = 0;
	for(int i = 0; i < p2.size(); i++)
	{
		int j = i;
		int p = 1;
		while(j < p2.size() && p2[j].first == p2[i].first)
		{
			p = p * p2[j].second % const1;
			j++;
		}
		int sum1 = 0;
		while(iter < Y && pointsy[iter].first < p2[i].first)
		{
			iter++;
		}
		while(iter < Y && pointsy[iter].first == p2[i].first)
		{
			sum1 += pointsy[iter].first + (pointsy[iter].second - 1) * (m);
			sum1 %= const1;
			iter++;
		}
		sum1 = (((n - 1) * m % const1 + 2 * p2[i].first) * n % const1) * inv2 % const1 - sum1;
		if(sum1 < 0)
		{
			sum1 += const1;
		}
		ans = ans - sum1;
		if(ans < 0)
		{
			ans += const1;
		}
		ans = (ans + sum1 * p) % const1;
		p2[i].second = p;
		i = j - 1;
	}
	for(int i = 0; i < X; i++)
	{
		int val = (pointsx[i].first - 1) * (m) + pointsx[i].second;
		val %= const1;
		ans -= val;
		if(ans < 0)
		{
			ans += const1;
		}
		int it1 = lower_bound(p1.begin(), p1.end(), make_pair(pointsx[i].first, 0LL)) - p1.begin();
		int it2 = lower_bound(p2.begin(), p2.end(), make_pair(pointsx[i].second, 0LL)) - p2.begin();
		val = val * p1[it1].second % const1 * p2[it2].second % const1;
		ans += val;
		if(ans >= const1)
		{
			ans -= const1;
		}
	}
	cout << ans;
    return 0;
}

Compilation message (stderr)

automobil.cpp: In function 'int main()':
automobil.cpp:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < p1.size(); i++)
                 ~~^~~~~~~~~~~
automobil.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < p2.size(); j++)
                  ~~^~~~~~~~~~~
automobil.cpp:61:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < p1.size(); i++)
                 ~~^~~~~~~~~~~
automobil.cpp:65:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j < p1.size() && p1[j].first == p1[i].first)
         ~~^~~~~~~~~~~
automobil.cpp:97:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < p2.size(); i++)
                 ~~^~~~~~~~~~~
automobil.cpp:101:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j < p2.size() && p2[j].first == p2[i].first)
         ~~^~~~~~~~~~~

• Subtask 1: 100 / 100