oj.uz

Submission #130375

# Submission time Handle Problem Language Result Execution time Memory
130375 2019-07-15T05:12:58 Z 김세빈(#3148) Dominance (CEOI08_dominance) C++14
100 / 100
 15 ms 1056 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;

struct edge{
	ll x, l, r, v;
	edge() {}
	edge(ll x, ll l, ll r, ll v) :
		x(x), l(l), r(r), v(v) {}
};

struct container{
	vector <edge> V[6060], E;
	vector <ll> X, Y;
	ll S[6060];
	ll w, b;
	
	void insert(ll x, ll l, ll r, ll v)
	{
		E.emplace_back(x, l, r, v);
		X.push_back(x);
		Y.push_back(l); Y.push_back(r);
	}
	
	void process()
	{
		ll i, j, s;
		
		sort(X.begin(), X.end());
		X.erase(unique(X.begin(), X.end()), X.end());
		
		sort(Y.begin(), Y.end());
		Y.erase(unique(Y.begin(), Y.end()), Y.end());
		
		for(edge &e: E){
			e.x = lower_bound(X.begin(), X.end(), e.x) - X.begin();
			e.l = lower_bound(Y.begin(), Y.end(), e.l) - Y.begin();
			e.r = lower_bound(Y.begin(), Y.end(), e.r) - Y.begin();
			V[e.x].emplace_back(e);
		}
		
		for(i=0; i<X.size(); i++){
			for(edge &e: V[i]){
				S[e.l] += e.v; S[e.r] -= e.v;
			}
			
			for(j=0, s=0; j<Y.size(); j++){
				s += S[j];
				if(s > 0) w += (X[i + 1] - X[i]) * (Y[j + 1] - Y[j]);
				else if(s < 0) b += (X[i + 1] - X[i]) * (Y[j + 1] - Y[j]);
			}
		}
	}
	
	ll getw() { return w; }
	ll getb() { return b; }
};

container T1, T2;
ll n;

int main()
{
	ll i, x, y, z, t;
	char ch[3];
	
	scanf("%lld%lld%lld", &n, &n, &n);
	
	for(i=0; i<n; i++){
		scanf("%s%lld%lld%lld", ch, &x, &y, &z);
		if(*ch == 'W') t = 1;
		else t = -1;
		
		if(x + y + z & 1){
			T2.insert(x + y - z + 1 >> 1, x - y - z + 1 >> 1, x - y + z + 3 >> 1, t);
			T2.insert(x + y + z + 3 >> 1, x - y - z + 1 >> 1, x - y + z + 3 >> 1, -t);
			
			T1.insert(x + y - z + 1 >> 1, x - y - z + 1 >> 1, x - y + z + 1 >> 1, t);
			T1.insert(x + y + z + 1 >> 1, x - y - z + 1 >> 1, x - y + z + 1 >> 1, -t);
		}
		else{
			T1.insert(x + y - z >> 1, x - y - z >> 1, x - y + z + 2 >> 1, t);
			T1.insert(x + y + z + 2 >> 1, x - y - z >> 1, x - y + z + 2 >> 1, -t);
			
			T2.insert(x + y - z + 2 >> 1, x - y - z + 2 >> 1, x - y + z + 2 >> 1, t);
			T2.insert(x + y + z + 2 >> 1, x - y - z + 2 >> 1, x - y + z + 2 >> 1, -t);
		}
	}
	
	T1.process(); T2.process();
	
	printf("%lld %lld\n", T1.getw() + T2.getw(), T1.getb() + T2.getb());
	
	return 0;
}

Compilation message

dominance.cpp: In member function 'void container::process()':
dominance.cpp:45:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0; i<X.size(); i++){
            ~^~~~~~~~~
dominance.cpp:50:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=0, s=0; j<Y.size(); j++){
                  ~^~~~~~~~~
dominance.cpp: In function 'int main()':
dominance.cpp:77:12: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   if(x + y + z & 1){
      ~~~~~~^~~
dominance.cpp:78:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    T2.insert(x + y - z + 1 >> 1, x - y - z + 1 >> 1, x - y + z + 3 >> 1, t);
              ~~~~~~~~~~^~~
dominance.cpp:78:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    T2.insert(x + y - z + 1 >> 1, x - y - z + 1 >> 1, x - y + z + 3 >> 1, t);
                                  ~~~~~~~~~~^~~
dominance.cpp:78:64: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    T2.insert(x + y - z + 1 >> 1, x - y - z + 1 >> 1, x - y + z + 3 >> 1, t);
                                                      ~~~~~~~~~~^~~
dominance.cpp:79:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    T2.insert(x + y + z + 3 >> 1, x - y - z + 1 >> 1, x - y + z + 3 >> 1, -t);
              ~~~~~~~~~~^~~
dominance.cpp:79:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    T2.insert(x + y + z + 3 >> 1, x - y - z + 1 >> 1, x - y + z + 3 >> 1, -t);
                                  ~~~~~~~~~~^~~
dominance.cpp:79:64: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    T2.insert(x + y + z + 3 >> 1, x - y - z + 1 >> 1, x - y + z + 3 >> 1, -t);
                                                      ~~~~~~~~~~^~~
dominance.cpp:81:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    T1.insert(x + y - z + 1 >> 1, x - y - z + 1 >> 1, x - y + z + 1 >> 1, t);
              ~~~~~~~~~~^~~
dominance.cpp:81:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    T1.insert(x + y - z + 1 >> 1, x - y - z + 1 >> 1, x - y + z + 1 >> 1, t);
                                  ~~~~~~~~~~^~~
dominance.cpp:81:64: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    T1.insert(x + y - z + 1 >> 1, x - y - z + 1 >> 1, x - y + z + 1 >> 1, t);
                                                      ~~~~~~~~~~^~~
dominance.cpp:82:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    T1.insert(x + y + z + 1 >> 1, x - y - z + 1 >> 1, x - y + z + 1 >> 1, -t);
              ~~~~~~~~~~^~~
dominance.cpp:82:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    T1.insert(x + y + z + 1 >> 1, x - y - z + 1 >> 1, x - y + z + 1 >> 1, -t);
                                  ~~~~~~~~~~^~~
dominance.cpp:82:64: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    T1.insert(x + y + z + 1 >> 1, x - y - z + 1 >> 1, x - y + z + 1 >> 1, -t);
                                                      ~~~~~~~~~~^~~
dominance.cpp:85:20: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
    T1.insert(x + y - z >> 1, x - y - z >> 1, x - y + z + 2 >> 1, t);
              ~~~~~~^~~
dominance.cpp:85:36: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
    T1.insert(x + y - z >> 1, x - y - z >> 1, x - y + z + 2 >> 1, t);
                              ~~~~~~^~~
dominance.cpp:85:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    T1.insert(x + y - z >> 1, x - y - z >> 1, x - y + z + 2 >> 1, t);
                                              ~~~~~~~~~~^~~
dominance.cpp:86:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    T1.insert(x + y + z + 2 >> 1, x - y - z >> 1, x - y + z + 2 >> 1, -t);
              ~~~~~~~~~~^~~
dominance.cpp:86:40: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
    T1.insert(x + y + z + 2 >> 1, x - y - z >> 1, x - y + z + 2 >> 1, -t);
                                  ~~~~~~^~~
dominance.cpp:86:60: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    T1.insert(x + y + z + 2 >> 1, x - y - z >> 1, x - y + z + 2 >> 1, -t);
                                                  ~~~~~~~~~~^~~
dominance.cpp:88:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    T2.insert(x + y - z + 2 >> 1, x - y - z + 2 >> 1, x - y + z + 2 >> 1, t);
              ~~~~~~~~~~^~~
dominance.cpp:88:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    T2.insert(x + y - z + 2 >> 1, x - y - z + 2 >> 1, x - y + z + 2 >> 1, t);
                                  ~~~~~~~~~~^~~
dominance.cpp:88:64: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    T2.insert(x + y - z + 2 >> 1, x - y - z + 2 >> 1, x - y + z + 2 >> 1, t);
                                                      ~~~~~~~~~~^~~
dominance.cpp:89:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    T2.insert(x + y + z + 2 >> 1, x - y - z + 2 >> 1, x - y + z + 2 >> 1, -t);
              ~~~~~~~~~~^~~
dominance.cpp:89:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    T2.insert(x + y + z + 2 >> 1, x - y - z + 2 >> 1, x - y + z + 2 >> 1, -t);
                                  ~~~~~~~~~~^~~
dominance.cpp:89:64: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    T2.insert(x + y + z + 2 >> 1, x - y - z + 2 >> 1, x - y + z + 2 >> 1, -t);
                                                      ~~~~~~~~~~^~~
dominance.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld", &n, &n, &n);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
dominance.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%lld%lld%lld", ch, &x, &y, &z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1016 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 10 ms 1016 KB Output is correct
5 Correct 11 ms 1056 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 7 ms 888 KB Output is correct
9 Correct 12 ms 1016 KB Output is correct
10 Correct 15 ms 1016 KB Output is correct
11 Correct 15 ms 1016 KB Output is correct
12 Correct 2 ms 636 KB Output is correct
13 Correct 13 ms 1016 KB Output is correct
14 Correct 2 ms 632 KB Output is correct
15 Correct 11 ms 1016 KB Output is correct
16 Correct 6 ms 1016 KB Output is correct
17 Correct 2 ms 632 KB Output is correct
18 Correct 3 ms 632 KB Output is correct
19 Correct 3 ms 760 KB Output is correct
20 Correct 4 ms 760 KB Output is correct