oj.uz

Submission #120558

# Submission time Handle Problem Language Result Execution time Memory
120558 2019-06-24T23:20:51 Z _Samir Automobil (COCI17_automobil) C++14
100 / 100
 81 ms 8312 KB 
/*
   we will use dp , our state will be left most house i visited , the right most house i visited and
   the time till now , each time will try to visit new house from the left or the right
*/
#include<queue>
#include<map>
#include <string>
#include<bits/stdc++.h>
#define pi 3.141592654
#define forr(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define input ios_base::sync_with_stdio(0);cin.tie(0);
//#define x real()
//#define y imag()
using namespace std;
typedef pair<double,double>pdd;
typedef long long  ll;
typedef pair<ll, ll>pii;
//typedef complex<double> point;
//template<typename T>T gcd(T x, T y) { if(y == 0)return x; else return gcd(y, x%y); }
//typedef bitset<30> mask;
//int x[8]={1,0,0,-1,-1,-1,1,1};
//int y[8]={0,1,-1,0,-1,1,-1,1};
//#define var(x) ((x)<<1)
//#define nvar(x) ((x)^1)
const int N=100000,M=100000;

ll n,m,k;
map<ll,ll>r,c;
ll sum,mod=1e9+7,R[1000004],pls;
 main()
{

//cout<<Pow((ll)1000000,(ll)110);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
//    char input[15];
//    scanf("%s", &input);  array of char
//  gets(c+1);  array of char
//printf("%s, ",name[k[i]].c_str());  printf of string
//priority_queue<ll,vector<ll>,greater<ll>>y;
input;

cin>>n>>m>>k;
for(ll i=1;i<=n;i++)
{
   R[i]=((i-1)*((m*m)%mod))%mod+(m*(m+1)/2)%mod;
   R[i]%=mod;
}


char t;
ll x,y;
forr(i,1,k)
{
    cin>>t>>x>>y;
    if(t=='S')
    {
        if(c.count(x)==0)c[x]=1;
        c[x]*=y;
        c[x]%=mod;
    }
    else
    {
        if(r.count(x)==0)r[x]=1;
        r[x]*=y;
        r[x]%=mod;
    }
}

for(auto b:c)
{
    ll g =(b.F*n)%mod+(((n*(n-1)/2)%mod)*m)%mod;
    g%=mod;
    for(auto a:r)
    {
        ll num=((a.F-1)*m)%mod+b.F;
        num%=mod;
        R[a.F]-=num;
        R[a.F]=(R[a.F]+mod)%mod;
        R[a.F]+=(num*b.S)%mod;
        R[a.F]%=mod;
        g-=num;
        g=(g+mod)%mod;
    }
    pls+=((b.S-1)*g)%mod;
    pls%=mod;
}

for(auto a:r)R[a.F]=(R[a.F]*a.S)%mod;

forr(i,1,n)
    sum=((sum%mod)+(R[i]%mod))%mod;

cout<<(sum+pls)%mod;
return 0;
}

Compilation message

automobil.cpp:32:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  main()
       ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 8 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 7 ms 384 KB Output is correct
10 Correct 9 ms 384 KB Output is correct
11 Correct 18 ms 1792 KB Output is correct
12 Correct 59 ms 5760 KB Output is correct
13 Correct 8 ms 512 KB Output is correct
14 Correct 52 ms 7032 KB Output is correct
15 Correct 50 ms 5120 KB Output is correct
16 Correct 79 ms 8184 KB Output is correct
17 Correct 81 ms 8184 KB Output is correct
18 Correct 80 ms 8224 KB Output is correct
19 Correct 81 ms 8192 KB Output is correct
20 Correct 81 ms 8312 KB Output is correct