Submission #143998

#	Time	Username	Problem	Language	Result	Execution time	Memory
143998		Ort	Automobil (COCI17_automobil)	C++11	0 / 100	19 ms	504 KiB

automobil

#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;

ll sol;
ll n, m, k, x, y;
ll sum_w;

char c;
vector<pll> upd_r, upd_c;
map<ll,ll> Mr, Mc;

inline ll mult(ll a, ll b) {
	return (a*b)%MOD;
}

inline ll add(ll a, ll b) {
	return (a+b+MOD)%MOD;
}

inline ll gauss(ll from, ll to, ll nums) {
	return mult( add(from, to) , nums )>>1;
}

inline ll val(ll y, ll 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++) {
		ll col = upd_c[i].fs;
		ll col_up = upd_c[i].sc;
		ll last_row = 1;
		for(int j=0;j<sz(upd_r);j++) {
			ll row = upd_r[j].fs;
			ll row_up = upd_r[j].sc;
			if(row==last_row) {
				ll 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) {
				ll c = val(last_row, col);
				sol = add(sol, mult(c,col_up) );
				sum_w = add(sum_w, c);
				last_row = row+1;
			}
			else {
				ll cl = val(last_row, col);
				ll ch = val(row-1, col);
				ll sum_range = gauss(cl, ch, row-last_row);
				ll mult_range = mult(sum_range, col_up);
				sol = add(sol, mult_range);
				sum_w = add(sum_w, sum_range);
				last_row = row+1;	
			}
			ll 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) {
			ll c = val(n, col);
			sol = add(sol, mult(c, col_up) );
			sum_w = add(sum_w, c);
		}
		else {
			ll cl = val(last_row, col);
			ll ch = val(n, col);
			ll sum_range = gauss(cl, ch, n-last_row+1);
			ll 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++) {
		ll row = upd_r[i].fs;
		ll row_up = upd_r[i].sc; ll last_col = 1;
		for(int j=0;j<sz(upd_c);j++) {
			ll col = upd_c[j].fs;
			ll col_up = upd_c[j].sc;
			if(last_col==col) {
				last_col = col + 1;
				continue;
			}
			else if(col==last_col+1) {
				ll c = val(row, last_col);
				sol = add(sol, mult(c,row_up) );
				sum_w = add(sum_w, c);
				last_col = col + 1;
				continue;
			}
			else {
				ll cl = val(row, last_col);
				ll ch = val(row, col-1);
				ll sum_range = gauss(cl, ch, col-last_col);
				ll 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) {
			ll c = val(row, m);
			sol = add(sol, mult(c,row_up) );
			sum_w = add(sum_w, c);
		}
		else {
			ll cl = val(row,last_col);
			ll ch = val(row, m);
			ll sum_range = gauss(cl, ch, m-last_col+1);
			ll mult_range = mult(sum_range, row_up);
			sol = add(sol, mult_range);
			sum_w = add(sum_w, sum_range);		
		}	
	}
	ll t = mult(n, m);
	ll total_no_update = mult(t, t+1)>>1;
	ll res = total_no_update - sum_w;
	cout << add(sol, res);
	return 0;
}

Compilation message (stderr)

automobil.cpp: In function 'int main()':
automobil.cpp:127:7: warning: unused variable 'col_up' [-Wunused-variable]
    ll col_up = upd_c[j].sc;
       ^~~~~~

• Subtask 1: 0 / 100