Submission #818981


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

struct SumSegTree{
    long n; vector<ll> dat;
    //初期化
    SumSegTree(long _n){
        n=1;
        while(n<_n) n*=2;
        dat=vector<ll>(2*n-1,0);
    }
    //k番目(0-indexed)の値をaを加える
    void update(long k, ll a){
        k+=n-1;
        dat[k]+=a;
        //更新
        while(k>0){
            k=(k-1)/2;
            dat[k]=dat[2*k+1]+dat[2*k+2];
        }
    }
    //内部的に投げられるクエリ
    ll _query(long a, long b, long k, long l, long r){
        if(r<=a || b<=l) return 0;

        if(a<=l && r<=b) return dat[k];
        else{
            ll vl=_query(a,b,2*k+1,l,(l+r)/2);
            ll vr=_query(a,b,2*k+2,(l+r)/2,r);
            return vl+vr;
        }
    }
    //[a,b)の和を求める
    ll query(long a, long b){
        return _query(a,b,0,0,n);
    }
};

const long N=200001;

int main()
{
    SumSegTree segt(N);

    int Q=0;
    cin >>Q;

    rep(q,Q)
    {
        int t,x;
        scanf(" %d %d", &t, &x);
        if(t==1) segt.update(x,1);
        else
        {
            int l=1, r=N;
            while(r-l>1)
            {
                int med=(l+r)/2;
                if(segt.query(1,med)<x) l=med;
                else r=med;
            }

            segt.update(l,-1);
            printf("%d\n", l);
        }
    }

    return 0;
}

Submission Info

Submission Time
Task C - データ構造
User imulan
Language C++11 (GCC 4.8.1)
Score 100
Code Size 1715 Byte
Status AC
Exec Time 920 ms
Memory 4980 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:60:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %d %d", &t, &x);
                                ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 16
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt
Case Name Status Exec Time Memory
sample_01.txt AC 36 ms 4964 KB
sample_02.txt AC 34 ms 4836 KB
subtask1_01.txt AC 34 ms 4964 KB
subtask1_02.txt AC 34 ms 4964 KB
subtask1_03.txt AC 34 ms 4968 KB
subtask1_04.txt AC 93 ms 4832 KB
subtask1_05.txt AC 166 ms 4968 KB
subtask1_06.txt AC 40 ms 4936 KB
subtask1_07.txt AC 327 ms 4964 KB
subtask1_08.txt AC 918 ms 4976 KB
subtask1_09.txt AC 916 ms 4960 KB
subtask1_10.txt AC 522 ms 4968 KB
subtask1_11.txt AC 521 ms 4968 KB
subtask1_12.txt AC 109 ms 4844 KB
subtask1_13.txt AC 920 ms 4968 KB
subtask1_14.txt AC 920 ms 4972 KB
subtask1_15.txt AC 783 ms 4972 KB
subtask1_16.txt AC 482 ms 4980 KB