Submission #378402

#	Time	Username	Problem	Language	Result	Execution time	Memory
378402		Karliver	Traffic (IOI10_traffic)	C++14	100 / 100	1483 ms	198124 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
#include <fstream>
#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;
typedef complex<ll> G;
const int INF = 1e9 + 1;
const int N = 100;
const double eps = 1e-3;

template <typename XPAX>
void ckma(XPAX &x, XPAX y) {
    x = (x < y ? y : x);
}
template <typename XPAX>
void ckmi(XPAX &x, XPAX y) {
    x = (x > y ? y : x);
}


ll power(ll a, ll b){
    if(!b)
        return 1;
    ll c=power(a,b/2);
    c=(1LL*c*c);
    if(b%2)
        c=(1LL*c*a);
    return c;
}


int mul(int a, int b) {
    return a * 1ll * b % mod;
}
int add(int a, int b) {
    int s = (a+b);
    if (s>=mod) s-=mod;
    return s;
}



struct RMQ {
    vector<vector<int>>st;
    RMQ(vector<int> &a) {
        int n = a.size();
        int k = ceil(log2(n));
        st.clear();
        st = vector<vector<int>>(n, vector<int>(k + 1, 0));
        for(int i = 0;i < n;++i) {
            st[i][0] = a[i];
        }
        for(int j = 1;j <= k;++j) {
            for(int i = 0;i + (1 << j) <= n;++i) {
                st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            }
        }

    }
    int rng_q(int l, int r) {
        if(l > r)return -1;
        int j = log2(r - l + 1);
        int ans = max(st[l][j], st[r - (1 << j) + 1][j]);
        return ans;
    }

};

template<long long mod = 1000000007>
struct modint{
	long long a;

	modint() : a(0){}
	modint(long long t){
		a = t % mod;
		if(a < 0) a += mod;
	}

	operator long long() const{ return a; }

	bool operator==(const modint &x) const{ return a == x.a; }
	bool operator!=(const modint &x) const{ return a != x.a; }

	modint operator-() const{ return modint(a ? (mod - a) : 0); }
	modint operator~() const{ return pow(mod - 2); }

	modint operator+(const modint &x) const{ return modint(*this) += x; }
	modint operator-(const modint &x) const{ return modint(*this) -= x; }
	modint operator*(const modint &x) const{ return modint(*this) *= x; }
	modint operator/(const modint &x) const{ return modint(*this) /= x; }

	modint &operator+=(const modint &x){
		a += x.a;
		if(a >= mod) a -= mod;
		return *this;
	}
	modint &operator-=(const modint &x){
		a -= x.a;
		if(a < 0) a += mod;
		return *this;
	}
	modint &operator*=(const modint &x){
		a = a * x.a % mod;
		return *this;
	}
	modint &operator/=(const modint &x){
		a = a * (~x).a % mod;
		return *this;
	}

	friend ostream &operator<<(ostream &os,const modint &x){
		return os << x.a;
	}
	friend istream &operator>>(istream &is,modint &x){
		long long t;
		is >> t;
		x = modint(t);
		return is;
	}

	modint pow(long long x) const{
		modint ret = 1,tmp = a;
		for(;x;tmp *= tmp,x >>= 1){
			if(x & 1) ret *= tmp;
		}
		return ret;
	}
};
const ll MOD = 1e9 + 7;
using Mint = modint<MOD>;


template<class T>
struct Combination{
	vector<T> fact,factinv;
	Combination(int n) : fact(n + 1),factinv(n + 1){
		fact[0] = 1;
		for(int i = 1;i <= n;i++) fact[i] = fact[i - 1] * T(i);
		factinv[n] = ~fact[n];
		for(int i = n;i >= 1;i--) factinv[i - 1] = factinv[i] * T(i);
	}
	T nCr(int n,int r){
		if(n < 0 || r < 0 || n < r) return 0;
		return fact[n]  * factinv[r] *  factinv[n - r];
	}
	T factorial(int x) {
        if(x < 0)return 0;
        return fact[x];
	}
};

void done() {


}


void solve()
{



    // 11000
    //
    // 4 3 5 2 1
    // -1 2 -3 -1
    //




}
int LocateCentre(int n, int p[], int s[], int d[]) {
    vector<vector<int>> g(n);
    forn(i, n - 1) {
        g[s[i]].push_back(d[i]);
        g[d[i]].push_back(s[i]);
    }
    vector<int> fans(n, 0);
    forn(i, n)fans[i] = p[i];
    function<void(int, int)> dfs = [&](int v, int par) {

        for(auto c : g[v]) {
            if(c != par) {
                dfs(c, v);
                fans[v] += fans[c];
            }
        }
    };
    int l = INT_MAX;
    dfs(0, -1);
    int ans = -1;
    function<void(int, int, int)> calc = [&](int v, int par, int pr) {
        int ms = 0;
        int d = pr;
        for(auto c : g[v]) {
            if(c != par) {

                ckma(ms, fans[c]);
                calc(c, v, d + (fans[v] - fans[c]));
            }
        }
        ckma(ms, pr);
        if(ms < l) {
            l = ms;
            ans = v;
        }


    };
    calc(0, -1, 0);

    return ans;
}

void emer() {





    // 3 4
    // 3 4 5
    //

    //
    // x + y = w + z
    // x =  w + z - y
    //
    int n;
    cin >> n;
    for(int i = 1;i <= 9;++i) cout << n * i << '\n';
}

void another() {

    // 10011
    //
    int n, q;
    cin>> n >> q;
    vector<int> c(n);
    for(int i = 0;i < n;++i) {
        cin >> c[i];
    }

    vector<vector<pair<int, pairs>>> qur(n);
    for(int i = 0;i < q;++i) {
        int l, r;
        cin>> l >> r;
        --l;
        --r;
        qur[r].push_back({l, {i, 1}});
        if(l) {
            qur[l - 1].push_back({l, {i, -1}});
        }
    }
    vector<int> f(n);

    auto inc = [&](int x) {
        for(; x < n;x = (x | (x + 1))) f[x]++;
    };
    auto get = [&](int  x) {
        int ans =0;
        for(; x >= 0;x = (x & (x + 1)) - 1)
            ans += f[x];
        return ans;
    };

    vector<int> ret(q);
    map<int, int> last;
    vector<int> pev(n, -1);

    for(int i = 0;i < n;++i) {
        if(last.count(c[i])) {
            pev[i] = last[c[i]];
        }
        last[c[i]] = i;
        inc(pev[i] + 1);
        for(auto c : qur[i]) {
            ret[c.second.first] += get(c.first) * c.second.second;
            //cout << ret[c.second.first] << '\n';

        }
    }

    forn(i, q) cout << ret[i] << '\n';

    // 1 6 4 1 2 2 8
    // (1, 3) (2, 5)
    // 3 0 0 0 0 0 0


}
void test_case() {
    int t;
    cin >> t;
    forn(p, t) {
        //cout << "Case #" << p + 1 << ": ";

        solve();

    }
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25