답안 #161319

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
161319 2019-11-01T19:58:01 Z Ort Automobil (COCI17_automobil) C++11
25 / 100
1000 ms 760 KB
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
#define MEM(a, b) memset(a, (b), sizeof(a))
#define ALL(c) (c).begin(),(c).end()
#define sz(a) ((int)(a.size()))
#define ll long long
#define LINF (ll)1e18
#define INF (int)1e9
#define MINF 0x3F3F3F3F
#define pb push_back
#define fs first
#define sc second
#define mp make_pair
#define MOD 1000000007
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MAX 1000005
#define watch(x) cerr<<#x<<" = "<<(x)<<endl;
 
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
template<class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

using namespace std;

const int base = 1000000000;
const int base_digits = 9; 
struct bigint {
    vector<int> a;
    int sign;
    int size(){
	if(a.empty())return 0;
	int ans=(a.size()-1)*base_digits;
	int ca=a.back();
	while(ca)
	    ans++,ca/=10;
	return ans;
    }
    bigint operator ^(const bigint &v){
	bigint ans=1,a=*this,b=v;
	while(!b.isZero()){
	    if(b%2)
		ans*=a;
	    a*=a,b/=2;
	}
	return ans;
    }
    string to_string(){
	stringstream ss;
	ss << *this;
	string s;
	ss >> s;
	return s;
    }
    int sumof(){
	string s = to_string();
	int ans = 0;
	for(auto c : s)  ans += c - '0';
	return ans;
    }
    /*</arpa>*/
    bigint() :
	sign(1) {
    }
 
    bigint(long long v) {
	*this = v;
    }
 
    bigint(const string &s) {
	read(s);
    }
 
    void operator=(const bigint &v) {
	sign = v.sign;
	a = v.a;
    }
 
    void operator=(long long v) {
	sign = 1;
	a.clear();
	if (v < 0)
	    sign = -1, v = -v;
	for (; v > 0; v = v / base)
	    a.push_back(v % base);
    }
 
    bigint operator+(const bigint &v) const {
	if (sign == v.sign) {
	    bigint res = v;
 
	    for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i) {
		if (i == (int) res.a.size())
		    res.a.push_back(0);
		res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
		carry = res.a[i] >= base;
		if (carry)
		    res.a[i] -= base;
	    }
	    return res;
	}
	return *this - (-v);
    }
 
    bigint operator-(const bigint &v) const {
	if (sign == v.sign) {
	    if (abs() >= v.abs()) {
		bigint res = *this;
		for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
		    res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
		    carry = res.a[i] < 0;
		    if (carry)
			res.a[i] += base;
		}
		res.trim();
		return res;
	    }
	    return -(v - *this);
	}
	return *this + (-v);
    }
 
    void operator*=(int v) {
	if (v < 0)
	    sign = -sign, v = -v;
	for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
	    if (i == (int) a.size())
		a.push_back(0);
	    long long cur = a[i] * (long long) v + carry;
	    carry = (int) (cur / base);
	    a[i] = (int) (cur % base);
	    //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
	}
	trim();
    }
 
    bigint operator*(int v) const {
	bigint res = *this;
	res *= v;
	return res;
    }
 
    void operator*=(long long v) {
	if (v < 0)
	    sign = -sign, v = -v;
	for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
	    if (i == (int) a.size())
		a.push_back(0);
	    long long cur = a[i] * (long long) v + carry;
	    carry = (int) (cur / base);
	    a[i] = (int) (cur % base);
	    //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
	}
	trim();
    }
 
    bigint operator*(long long v) const {
	bigint res = *this;
	res *= v;
	return res;
    }
 
    friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
	int norm = base / (b1.a.back() + 1);
	bigint a = a1.abs() * norm;
	bigint b = b1.abs() * norm;
	bigint q, r;
	q.a.resize(a.a.size());
 
	for (int i = a.a.size() - 1; i >= 0; i--) {
	    r *= base;
	    r += a.a[i];
	    int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
	    int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
	    int d = ((long long) base * s1 + s2) / b.a.back();
	    r -= b * d;
	    while (r < 0)
		r += b, --d;
	    q.a[i] = d;
	}
 
	q.sign = a1.sign * b1.sign;
	r.sign = a1.sign;
	q.trim();
	r.trim();
	return make_pair(q, r / norm);
    }
 
    bigint operator/(const bigint &v) const {
	return divmod(*this, v).first;
    }
 
    bigint operator%(const bigint &v) const {
	return divmod(*this, v).second;
    }
 
    void operator/=(int v) {
	if (v < 0)
	    sign = -sign, v = -v;
	for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
	    long long cur = a[i] + rem * (long long) base;
	    a[i] = (int) (cur / v);
	    rem = (int) (cur % v);
	}
	trim();
    }
 
    bigint operator/(int v) const {
	bigint res = *this;
	res /= v;
	return res;
    }
 
    int operator%(int v) const {
	if (v < 0)
	    v = -v;
	int m = 0;
	for (int i = a.size() - 1; i >= 0; --i)
	    m = (a[i] + m * (long long) base) % v;
	return m * sign;
    }
 
    void operator+=(const bigint &v) {
	*this = *this + v;
    }
    void operator-=(const bigint &v) {
	*this = *this - v;
    }
    void operator*=(const bigint &v) {
	*this = *this * v;
    }
    void operator/=(const bigint &v) {
	*this = *this / v;
    }
 
    bool operator<(const bigint &v) const {
	if (sign != v.sign)
	    return sign < v.sign;
	if (a.size() != v.a.size())
	    return a.size() * sign < v.a.size() * v.sign;
	for (int i = a.size() - 1; i >= 0; i--)
	    if (a[i] != v.a[i])
		return a[i] * sign < v.a[i] * sign;
	return false;
    }
 
    bool operator>(const bigint &v) const {
	return v < *this;
    }
    bool operator<=(const bigint &v) const {
	return !(v < *this);
    }
    bool operator>=(const bigint &v) const {
	return !(*this < v);
    }
    bool operator==(const bigint &v) const {
	return !(*this < v) && !(v < *this);
    }
    bool operator!=(const bigint &v) const {
	return *this < v || v < *this;
    }
 
    void trim() {
	while (!a.empty() && !a.back())
	    a.pop_back();
	if (a.empty())
	    sign = 1;
    }
 
    bool isZero() const {
	return a.empty() || (a.size() == 1 && !a[0]);
    }
 
    bigint operator-() const {
	bigint res = *this;
	res.sign = -sign;
	return res;
    }
 
    bigint abs() const {
	bigint res = *this;
	res.sign *= res.sign;
	return res;
    }
 
    long long longValue() const {
	long long res = 0;
	for (int i = a.size() - 1; i >= 0; i--)
	    res = res * base + a[i];
	return res * sign;
    }
 
    friend bigint gcd(const bigint &a, const bigint &b) {
	return b.isZero() ? a : gcd(b, a % b);
    }
    friend bigint lcm(const bigint &a, const bigint &b) {
	return a / gcd(a, b) * b;
    }
 
    void read(const string &s) {
	sign = 1;
	a.clear();
	int pos = 0;
	while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
	    if (s[pos] == '-')
		sign = -sign;
	    ++pos;
	}
	for (int i = s.size() - 1; i >= pos; i -= base_digits) {
	    int x = 0;
	    for (int j = max(pos, i - base_digits + 1); j <= i; j++)
		x = x * 10 + s[j] - '0';
	    a.push_back(x);
	}
	trim();
    }
 
    friend istream& operator>>(istream &stream, bigint &v) {
	string s;
	stream >> s;
	v.read(s);
	return stream;
    }
 
    friend ostream& operator<<(ostream &stream, const bigint &v) {
	if (v.sign == -1)
	    stream << '-';
	stream << (v.a.empty() ? 0 : v.a.back());
	for (int i = (int) v.a.size() - 2; i >= 0; --i)
	    stream << setw(base_digits) << setfill('0') << v.a[i];
	return stream;
    }
 
    static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
	vector<long long> p(max(old_digits, new_digits) + 1);
	p[0] = 1;
	for (int i = 1; i < (int) p.size(); i++)
	    p[i] = p[i - 1] * 10;
	vector<int> res;
	long long cur = 0;
	int cur_digits = 0;
	for (int i = 0; i < (int) a.size(); i++) {
	    cur += a[i] * p[cur_digits];
	    cur_digits += old_digits;
	    while (cur_digits >= new_digits) {
		res.push_back(int(cur % p[new_digits]));
		cur /= p[new_digits];
		cur_digits -= new_digits;
	    }
	}
	res.push_back((int) cur);
	while (!res.empty() && !res.back())
	    res.pop_back();
	return res;
    }
 
    typedef vector<long long> vll;
 
    static vll karatsubaMultiply(const vll &a, const vll &b) {
	int n = a.size();
	vll res(n + n);
	if (n <= 32) {
	    for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		    res[i + j] += a[i] * b[j];
	    return res;
	}
 
	int k = n >> 1;
	vll a1(a.begin(), a.begin() + k);
	vll a2(a.begin() + k, a.end());
	vll b1(b.begin(), b.begin() + k);
	vll b2(b.begin() + k, b.end());
 
	vll a1b1 = karatsubaMultiply(a1, b1);
	vll a2b2 = karatsubaMultiply(a2, b2);
 
	for (int i = 0; i < k; i++)
	    a2[i] += a1[i];
	for (int i = 0; i < k; i++)
	    b2[i] += b1[i];
 
	vll r = karatsubaMultiply(a2, b2);
	for (int i = 0; i < (int) a1b1.size(); i++)
	    r[i] -= a1b1[i];
	for (int i = 0; i < (int) a2b2.size(); i++)
	    r[i] -= a2b2[i];
 
	for (int i = 0; i < (int) r.size(); i++)
	    res[i + k] += r[i];
	for (int i = 0; i < (int) a1b1.size(); i++)
	    res[i] += a1b1[i];
	for (int i = 0; i < (int) a2b2.size(); i++)
	    res[i + n] += a2b2[i];
	return res;
    }
 
    bigint operator*(const bigint &v) const {
	vector<int> a6 = convert_base(this->a, base_digits, 6);
	vector<int> b6 = convert_base(v.a, base_digits, 6);
	vll a(a6.begin(), a6.end());
	vll b(b6.begin(), b6.end());
	while (a.size() < b.size())
	    a.push_back(0);
	while (b.size() < a.size())
	    b.push_back(0);
	while (a.size() & (a.size() - 1))
	    a.push_back(0), b.push_back(0);
	vll c = karatsubaMultiply(a, b);
	bigint res;
	res.sign = sign * v.sign;
	for (int i = 0, carry = 0; i < (int) c.size(); i++) {
	    long long cur = c[i] + carry;
	    res.a.push_back((int) (cur % 1000000));
	    carry = (int) (cur / 1000000);
	}
	res.a = convert_base(res.a, 6, base_digits);
	res.trim();
	return res;
    }
};


bigint sol;
bigint n, m;
ll k, x, y;
bigint sum_w;
 
char c;
vector<pair<bigint,bigint> > upd_r, upd_c;
map<bigint,bigint> Mr, Mc;
 
inline bigint mult(bigint a, bigint b) {
	return (a*b)%MOD;
}
 
inline bigint add(bigint a, bigint b) {
	return (a+b+MOD)%MOD;
}
 
inline bigint gauss(bigint from, bigint to, bigint nums) {
	return mult( add(from, to) , nums ) / 2;
}
 
inline bigint val(bigint y, bigint x) {
	return add( mult(y-1, m),x);
}
 
 
int main() {
	cin >> n >> m >> k;
	for(int i=0;i<k;i++) {
		cin >> c >> x >> y;
		if(c=='R') {
			if(Mr.find(x)==Mr.end()) Mr[x] = y;
			else Mr[x] *= y;
		}
		else {
			if(Mc.find(x)==Mc.end()) Mc[x] = y;
			else Mc[x] *= y;
		}
	}
	for(auto x:Mr) upd_r.pb(mp(x.first,x.second));
	for(auto x:Mc) upd_c.pb(mp(x.first,x.second));
	
	
	
	sort(ALL(upd_r)); sort(ALL(upd_c));
	for(int i=0;i<sz(upd_c);i++) {
		bigint col = upd_c[i].fs;
		bigint col_up = upd_c[i].sc;
		bigint last_row = 1;
		for(int j=0;j<sz(upd_r);j++) {
			bigint row = upd_r[j].fs;
			bigint row_up = upd_r[j].sc;
			if(row==last_row) {
				bigint c = val(row, col);
				sol = add(sol, mult(c, mult(col_up,row_up) ) );
				sum_w = add(sum_w, c);
				last_row = row+1;
				continue;
			}
			else if(row==last_row+1) {
				bigint c = val(last_row, col);
				sol = add(sol, mult(c,col_up) );
				sum_w = add(sum_w, c);
				last_row = row+1;
			}
			else {
				bigint cl = val(last_row, col);
				bigint ch = val(row-1, col);
				bigint sum_range = gauss(cl, ch, row-last_row);
				bigint mult_range = mult(sum_range, col_up);
				sol = add(sol, mult_range);
				sum_w = add(sum_w, sum_range);
				last_row = row+1;	
			}
			bigint c = val(row, col);
			sol = add(sol, mult(c, mult(col_up,row_up) ) );
			sum_w = add(sum_w, c);
			last_row = row+1;
		}
		if(last_row>n) continue;
		else if(last_row==n) {
			bigint c = val(n, col);
			sol = add(sol, mult(c, col_up) );
			sum_w = add(sum_w, c);
		}
		else {
			bigint cl = val(last_row, col);
			bigint ch = val(n, col);
			bigint sum_range = gauss(cl, ch, n-last_row+1);
			bigint mult_range = mult(sum_range, col_up);
			sol = add(sol, mult_range);
			sum_w = add(sum_w, sum_range);
		}
	}
	for(int i=0;i<sz(upd_r);i++) {
		bigint row = upd_r[i].fs;
		bigint row_up = upd_r[i].sc; bigint last_col = 1;
		for(int j=0;j<sz(upd_c);j++) {
			bigint col = upd_c[j].fs;
			bigint col_up = upd_c[j].sc;
			if(last_col==col) {
				last_col = col + 1;
				continue;
			}
			else if(col==last_col+1) {
				bigint c = val(row, last_col);
				sol = add(sol, mult(c,row_up) );
				sum_w = add(sum_w, c);
				last_col = col + 1;
				continue;
			}
			else {
				bigint cl = val(row, last_col);
				bigint ch = val(row, col-1);
				bigint sum_range = gauss(cl, ch, col-last_col);
				bigint mult_range = mult(sum_range, row_up);
				sol = add(sol, mult_range);
				sum_w = add(sum_w, sum_range);
				last_col = col+1;
			}
		}
		if(last_col>m) continue;
		else if(last_col==m) {
			bigint c = val(row, m);
			sol = add(sol, mult(c,row_up) );
			sum_w = add(sum_w, c);
		}
		else {
			bigint cl = val(row,last_col);
			bigint ch = val(row, m);
			bigint sum_range = gauss(cl, ch, m-last_col+1);
			bigint mult_range = mult(sum_range, row_up);
			sol = add(sol, mult_range);
			sum_w = add(sum_w, sum_range);		
		}	
	}
	bigint t = mult(n, m);
	bigint total_no_update = mult(t, t+1) / 2;
	bigint res = total_no_update - sum_w;
	cout << add(sol, res);
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 81 ms 376 KB Output isn't correct
2 Incorrect 638 ms 632 KB Output isn't correct
3 Correct 55 ms 380 KB Output is correct
4 Correct 166 ms 480 KB Output is correct
5 Correct 575 ms 548 KB Output is correct
6 Correct 229 ms 504 KB Output is correct
7 Incorrect 930 ms 624 KB Output isn't correct
8 Correct 301 ms 504 KB Output is correct
9 Incorrect 713 ms 632 KB Output isn't correct
10 Execution timed out 1025 ms 504 KB Time limit exceeded
11 Execution timed out 1075 ms 504 KB Time limit exceeded
12 Execution timed out 1084 ms 632 KB Time limit exceeded
13 Incorrect 968 ms 632 KB Output isn't correct
14 Incorrect 29 ms 376 KB Output isn't correct
15 Execution timed out 1069 ms 632 KB Time limit exceeded
16 Execution timed out 1084 ms 760 KB Time limit exceeded
17 Execution timed out 1083 ms 632 KB Time limit exceeded
18 Execution timed out 1087 ms 632 KB Time limit exceeded
19 Execution timed out 1085 ms 632 KB Time limit exceeded
20 Execution timed out 1076 ms 632 KB Time limit exceeded