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 |
|
|
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 |