東京大学プログラミングコンテスト2014

Submission #3887967

Source codeソースコード

#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define int long long

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 200005;

set<P> st;
set<int> pl[MAX_N];

template<typename V> class BIT {
private:
	int n; vector<V> bit;
public:
	void add(int i,V x){ i++; while(i < n) bit[i] += x, i += i & -i;}
	V sum(int i){ i++; V s = 0; while(i>0) s += bit[i], i -= i & -i; return s;} //0_indexedで[0,i]の要素の和
	BIT(){} BIT(int sz){ n = sz + 1, bit.resize(n,0);} //初期値がすべて0の場合
	BIT(vector<V>& v){ n = (int)v.size()+1; bit.resize(n, 0); rep(i,n-1) add(i,v[i]);}
    void resize(int sz){ n = sz + 1, bit.resize(n,0); }
	void print(){ rep(i,n-1)cout<<sum(i)-sum(i-1)<< " ";cout<<endl;}
	void print_sum(){ rep(i,n)cout<<sum(i-1)<<" ";cout<<endl;}	//-1スタート
};

template<typename T> class segtree1 {
private:
    int n,sz;
    vector<T> node;
public:
    segtree1(vector<T>& v){
        sz = (int)v.size();
        n = 1;
        while(n < sz){
            n *= 2;
        }
        node.assign(2*n,numeric_limits<T>::max());
        rep(i,sz){
            node[i+n] = v[i];
        }
        for(int i=n-1; i>=1; i--){
            node[i] = min(node[2*i],node[2*i+1]);
        }
    }
    void update(int k,T a)
    {
    	node[k+=n] = a;
    	while(k>>=1){
    		node[k] = min(node[2*k],node[2*k+1]);
    	}
    }
    T query(int a,int b)
    {
        T res1 = numeric_limits<T>::max();
        T res2 = numeric_limits<T>::max();
        a += n, b += n;
        while(a != b){
            if(a % 2) res1 = min(res1, node[a++]);
            if(b % 2) res2 = min(res2, node[--b]);
            a >>= 1, b>>= 1;
        }
        return min(res1, res2);
    }
    void print()
    {
        rep(i,sz){
            cout << query(i,i+1) << " ";
        }
        cout << endl;
    }
};

template<typename T> class segtree2 {
private:
    int n,sz;
    vector<T> node;
public:
    segtree2(vector<T>& v){
        sz = (int)v.size();
        n = 1;
        while(n < sz){
            n *= 2;
        }
        node.assign(2*n,numeric_limits<T>::min());
        rep(i,sz){
            node[i+n] = v[i];
        }
        for(int i=n-1; i>=1; i--){
            node[i] = max(node[2*i],node[2*i+1]);
        }
    }
    void update(int k, T a)
    {
    	node[k+=n] = a;
    	while(k>>=1){
    		node[k] = max(node[2*k],node[2*k+1]);
    	}
    }
    T query(int a,int b)
    {
        T res1 = numeric_limits<T>::min();
        T res2 = numeric_limits<T>::min();
        a += n, b += n;
        while(a != b){
            if(a % 2) res1 = max(res1, node[a++]);
            if(b % 2) res2 = max(res2, node[--b]);
            a >>= 1, b>>= 1;
        }
        return max(res1, res2);
    }
    void print()
    {
        rep(i,sz){
            cout << query(i,i+1) << " ";
        }
        cout << endl;
    }
};

BIT<ll> bt;
BIT<int> cnt;

ll calc(int pos)
{
    ll x1 = bt.sum(pos), x2 = bt.sum(199999);
    ll y1 = cnt.sum(pos), y2 = cnt.sum(199999);
    return (ll)pos * y1 - x1 + (x2-x1) - (ll)pos * (y2-y1);
}

P get(int kind, segtree1<int>& sg1, segtree2<int>& sg2)
{
    return P(min(sg1.query(0, kind), sg1.query(kind+1, 200000)), max(sg2.query(0, kind), sg2.query(kind+1, 200000)));
}

ll solve()
{
    int l = 0, h = 200000LL;
    ll fl = calc(l);
    while(h-l>2){
        int m1 = (2*l+h)/3, m2 = (l+2*h)/3;
        ll f1 = calc(m1), f2 = calc(m2);
        if(f1 == f2) return f1;
        if(f1 < f2){
            h = m2;
        }else{
            l = m1, fl = f1;
        }
    }
    return min({fl, fl+1, calc(min(h, 199999LL))});
}

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    bt.resize(200000), cnt.resize(200000);
    vi hoge1(200000, INF), hoge2(200000, -INF);
    segtree1<int> left(hoge1);
    segtree2<int> right(hoge2);
    rep(i,n){
        int x,a;
        cin >> x >> a;
        --a;
        st.insert(P(x, a));
        pl[a].insert(x);
        if(*(--pl[a].end()) == x){
            right.update(a, x);
        }
        if(*pl[a].begin() == x){
            left.update(a, x);
        }
        bt.add(a,a), cnt.add(a,1);
    }
    int q;
    cin >> q;
    rep(i,q){
        int c,a,b;
        cin >> c >> a >> b;
        --b;
        if(c == 1){
            st.insert(P(a, b));
            pl[b].insert(a);
            if(*(--pl[b].end()) == a){
                right.update(b, a);
            }
            if(*pl[b].begin() == a){
                left.update(b, a);
            }
            bt.add(b,b);
            cnt.add(b,1);
        }else{
            st.erase(P(a, b));
            if((int)pl[b].size() == 1){
                right.update(b, -INF), left.update(b, INF);
            }else{
                if(*(--pl[b].end()) == a){
                    right.update(b, *(--(--pl[b].end())));
                }
                if(*pl[b].begin() == a){
                    left.update(b, *(++pl[b].begin()));
                }
            }
            pl[b].erase(a);
            bt.add(b,-b);
            cnt.add(b,-1);
        }
        // 右端に変えたとき
        int c1 = (*(--st.end())).se;
        P p1 = get(c1, left, right);
        if(p1.fi == INF){
            cout << "0\n";
            continue;
        }
        ll ans1 = p1.se-p1.fi+min(max(-p1.fi,p1.fi),max(-p1.se,p1.se)) + calc(c1);
        // 左端に変えたとき
        int c2 = (*st.begin()).se;
        P p2 = get(c2, left, right);
        if(p2.fi == INF){
            cout << "0\n";
            continue;
        }
        ll ans2 = p2.se-p2.fi+min(max(-p2.fi,p2.fi),max(-p2.se,p2.se)) + calc(c2);
        int L = (*st.begin()).fi, R = (*(--st.end())).fi;
        ll ans3 = R-L+min(max(-L,L),max(-R,R)) + solve();
        cout << min({ans1, ans2, ans3}) << "\n";
    }
    return 0;
}

Submission

Task問題 J - 看板の塗り替え
User nameユーザ名 kopricky
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 30
Source lengthソースコード長 7288 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Subtask 30 / 30 subtask_00.txt,subtask_01.txt,subtask_02.txt,subtask_03.txt,subtask_04.txt,subtask_05.txt,subtask_06.txt,subtask_07.txt,subtask_08.txt,subtask_09.txt,subtask_10.txt,subtask_11.txt,subtask_12.txt,subtask_13.txt,subtask_14.txt,subtask_15.txt,subtask_16.txt,subtask_17.txt,subtask_18.txt,subtask_19.txt,subtask_20.txt,subtask_21.txt,subtask_22.txt,subtask_23.txt,subtask_24.txt,subtask_25.txt
All 0 / 270 scrambled_00.txt,scrambled_01.txt,scrambled_02.txt,scrambled_03.txt,scrambled_04.txt,scrambled_05.txt,scrambled_06.txt,scrambled_07.txt,scrambled_08.txt,scrambled_09.txt,scrambled_10.txt,scrambled_11.txt,scrambled_12.txt,scrambled_13.txt,scrambled_14.txt,scrambled_15.txt,scrambled_16.txt,scrambled_17.txt,scrambled_18.txt,scrambled_19.txt,scrambled_20.txt,scrambled_21.txt,scrambled_22.txt,scrambled_23.txt,scrambled_24.txt,scrambled_25.txt,scrambled_26.txt,subtask_00.txt,subtask_01.txt,subtask_02.txt,subtask_03.txt,subtask_04.txt,subtask_05.txt,subtask_06.txt,subtask_07.txt,subtask_08.txt,subtask_09.txt,subtask_10.txt,subtask_11.txt,subtask_12.txt,subtask_13.txt,subtask_14.txt,subtask_15.txt,subtask_16.txt,subtask_17.txt,subtask_18.txt,subtask_19.txt,subtask_20.txt,subtask_21.txt,subtask_22.txt,subtask_23.txt,subtask_24.txt,subtask_25.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
scrambled_00.txt AC 12 ms 24064 KB
scrambled_01.txt AC 464 ms 47104 KB
scrambled_02.txt AC 321 ms 37888 KB
scrambled_03.txt AC 224 ms 35456 KB
scrambled_04.txt AC 144 ms 31616 KB
scrambled_05.txt AC 144 ms 35328 KB
scrambled_06.txt AC 420 ms 36096 KB
scrambled_07.txt AC 49 ms 25728 KB
scrambled_08.txt AC 337 ms 35072 KB
scrambled_09.txt AC 188 ms 30592 KB
scrambled_10.txt AC 63 ms 28800 KB
scrambled_11.txt AC 223 ms 35328 KB
scrambled_12.txt AC 140 ms 33920 KB
scrambled_13.txt AC 52 ms 26752 KB
scrambled_14.txt AC 114 ms 33536 KB
scrambled_15.txt AC 68 ms 27392 KB
scrambled_16.txt WA
scrambled_17.txt WA
scrambled_18.txt WA
scrambled_19.txt AC 240 ms 28032 KB
scrambled_20.txt AC 116 ms 27392 KB
scrambled_21.txt WA
scrambled_22.txt AC 429 ms 36096 KB
scrambled_23.txt AC 110 ms 26752 KB
scrambled_24.txt AC 357 ms 33536 KB
scrambled_25.txt AC 240 ms 30848 KB
scrambled_26.txt AC 270 ms 26368 KB
subtask_00.txt AC 19 ms 24576 KB
subtask_01.txt AC 18 ms 24448 KB
subtask_02.txt AC 18 ms 24320 KB
subtask_03.txt AC 14 ms 24192 KB
subtask_04.txt AC 15 ms 24320 KB
subtask_05.txt AC 18 ms 24320 KB
subtask_06.txt AC 14 ms 24192 KB
subtask_07.txt AC 18 ms 24320 KB
subtask_08.txt AC 13 ms 24192 KB
subtask_09.txt AC 14 ms 24192 KB
subtask_10.txt AC 14 ms 24320 KB
subtask_11.txt AC 13 ms 24064 KB
subtask_12.txt AC 14 ms 24320 KB
subtask_13.txt AC 12 ms 24192 KB
subtask_14.txt AC 13 ms 24064 KB
subtask_15.txt AC 18 ms 24320 KB
subtask_16.txt AC 16 ms 24320 KB
subtask_17.txt AC 15 ms 24192 KB
subtask_18.txt AC 13 ms 24192 KB
subtask_19.txt AC 18 ms 24320 KB
subtask_20.txt AC 19 ms 24576 KB
subtask_21.txt AC 19 ms 24320 KB
subtask_22.txt AC 16 ms 24192 KB
subtask_23.txt AC 17 ms 24192 KB
subtask_24.txt AC 13 ms 24192 KB
subtask_25.txt AC 16 ms 24192 KB