oj.uz

답안 #239321

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
239321 2020-06-15T11:32:50 Z MrRobot_28 Automobil (COCI17_automobil) C++17
100 / 100
 70 ms 8496 KB 
#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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1020 KB Output is correct
2 Correct 26 ms 3640 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 37 ms 6676 KB Output is correct
5 Correct 20 ms 3612 KB Output is correct
6 Correct 10 ms 1316 KB Output is correct
7 Correct 35 ms 6708 KB Output is correct
8 Correct 14 ms 2084 KB Output is correct
9 Correct 29 ms 3768 KB Output is correct
10 Correct 43 ms 6712 KB Output is correct
11 Correct 24 ms 3516 KB Output is correct
12 Correct 61 ms 7724 KB Output is correct
13 Correct 17 ms 2076 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 46 ms 6676 KB Output is correct
16 Correct 65 ms 8372 KB Output is correct
17 Correct 65 ms 8496 KB Output is correct
18 Correct 70 ms 8368 KB Output is correct
19 Correct 65 ms 8368 KB Output is correct
20 Correct 67 ms 8372 KB Output is correct