Submission #144023

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
144023	2019-08-15T17:13:32 Z	Ort	Automobil (COCI17_automobil)	Python 3	70 / 100	1000 ms	3796 KB

automobil

from sys import stdin, stdout

def gauss(fr,to,nums):
    return ((fr+to)*nums)//2

def val(y,x):
    return (y-1)*m + x


n, m, k = map(int,input().split());

Mr = dict();
Mc = dict();

for i in range(k):
    arr = [str(x) for x in stdin.readline().split()]
    c = arr[0]
    x = int(arr[1]); y = int(arr[2]);
    if(c=='R'):
        try: Mr[x]*=y
        except KeyError: Mr[x]=y
    if(c=='S'):
        try: Mc[x]*=y
        except KeyError: Mc[x]=y

upd_r = list(Mr.items())
upd_c = list(Mc.items())
upd_r.sort(); upd_c.sort();

sol = 0;
sum_w = 0;

for col, col_up in upd_c:
    last_row = 1;
    for row, row_up in upd_r:
        if(row==last_row):
            c = val(row,col);
            sol = sol + (c*row_up*col_up);
            sum_w = sum_w + c;
            last_row = row+1;
            continue;
        elif(row==last_row+1):
            c = val(last_row,col);
            sol = sol + (c*col_up);
            sum_w = sum_w+c;
            last_row = row+1;
        else:
            cl = val(last_row, col);
            ch = val(row-1, col);
            sum_range = gauss(cl,ch,row-last_row);
            mult_range = sum_range * col_up;
            sol = sol + mult_range;
            sum_w = sum_w + sum_range;
            last_row = row+1;
        c = val(row,col);
        sol = sol + (c*col_up*row_up);
        sum_w = sum_w + c;
        last_row = row + 1;
    if(last_row>n):
        continue;
    elif(last_row==n):
        c = val(n, col);
        sol = sol + (c*col_up);
        sum_w = sum_w+c;
    else:
        cl = val(last_row, col);
        ch = val(n, col);
        sum_range = gauss(cl,ch,n-last_row+1);
        mult_range = sum_range*col_up
        sol = sol+mult_range
        sum_w = sum_w+sum_range
for row, row_up in upd_r:
    last_col = 1;
    for col, col_up in upd_c:
        if(last_col==col):
            last_col = col+1;
            continue;
        elif(col==last_col+1):
            c = val(row, last_col);
            sol = sol + (c*row_up);
            sum_w = sum_w + c;
            last_col = col+1;
            continue;
        else:
            cl = val(row, last_col)
            ch = val(row,col-1)
            sum_range = gauss(cl,ch,col-last_col)
            mult_range = sum_range * row_up
            sol = sol + mult_range;
            sum_w = sum_w + sum_range
            last_col = col+1;
    if(last_col>m):
        continue;
    elif(last_col==m):
        c = val(row, m);
        sol = sol + (c*row_up);
        sum_w = sum_w+c;
    else:
        cl = val(row,last_col);
        ch = val(row,m);
        sum_range = gauss(cl,ch,m-last_col+1);
        mult_range = sum_range * row_up;
        sol = sol + mult_range;
        sum_w = sum_w + sum_range;
t = n * m;
total_no_update = (t*(t+1))//2
res = total_no_update - sum_w;
sol = sol+res;
stdout.write(str(sol%1000000007)) 

        

Subtask #1

70.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	3556 KB	Output is correct
2	Correct	193 ms	3796 KB	Output is correct
3	Correct	41 ms	3556 KB	Output is correct
4	Correct	62 ms	3548 KB	Output is correct
5	Correct	180 ms	3684 KB	Output is correct
6	Correct	84 ms	3612 KB	Output is correct
7	Correct	265 ms	3684 KB	Output is correct
8	Correct	104 ms	3556 KB	Output is correct
9	Correct	207 ms	3648 KB	Output is correct
10	Correct	293 ms	3664 KB	Output is correct
11	Correct	438 ms	3656 KB	Output is correct
12	Execution timed out	1077 ms	3684 KB	Time limit exceeded
13	Correct	290 ms	3556 KB	Output is correct
14	Correct	34 ms	3556 KB	Output is correct
15	Correct	897 ms	3684 KB	Output is correct
16	Execution timed out	1081 ms	3684 KB	Time limit exceeded
17	Execution timed out	1076 ms	3684 KB	Time limit exceeded
18	Execution timed out	1082 ms	3684 KB	Time limit exceeded
19	Execution timed out	1073 ms	3684 KB	Time limit exceeded
20	Execution timed out	1076 ms	3684 KB	Time limit exceeded