Submission #144017

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
144017	2019-08-15T16:55:24 Z	Ort	Automobil (COCI17_automobil)	Python 3	70 / 100	1000 ms	3784 KB

automobil

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):
    c, x, y = map(str,input().split());
    x = int(x); y = int(y);
    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;
print(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	190 ms	3684 KB	Output is correct
3	Correct	40 ms	3556 KB	Output is correct
4	Correct	64 ms	3556 KB	Output is correct
5	Correct	176 ms	3684 KB	Output is correct
6	Correct	83 ms	3556 KB	Output is correct
7	Correct	264 ms	3556 KB	Output is correct
8	Correct	108 ms	3556 KB	Output is correct
9	Correct	210 ms	3684 KB	Output is correct
10	Correct	297 ms	3688 KB	Output is correct
11	Correct	447 ms	3560 KB	Output is correct
12	Execution timed out	1070 ms	3684 KB	Time limit exceeded
13	Correct	288 ms	3684 KB	Output is correct
14	Correct	35 ms	3684 KB	Output is correct
15	Correct	902 ms	3784 KB	Output is correct
16	Execution timed out	1081 ms	3684 KB	Time limit exceeded
17	Execution timed out	1075 ms	3684 KB	Time limit exceeded
18	Execution timed out	1075 ms	3684 KB	Time limit exceeded
19	Execution timed out	1065 ms	3684 KB	Time limit exceeded
20	Execution timed out	1067 ms	3684 KB	Time limit exceeded