結果

問題 No.59 鉄道の旅
ユーザー kuuso1
提出日時 2014-11-06 23:48:49
言語 C#
(csc 3.4.0-beta4-19569-03)
結果
AC  
実行時間 88 ms
コード長 1,661 Byte
コンパイル時間 2,096 ms
使用メモリ 24,212 KB
最終ジャッジ日時 2020-01-14 13:30:41

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample1.txt AC 24 ms
17,492 KB
sample2.txt AC 24 ms
17,704 KB
sample3.txt AC 24 ms
17,456 KB
sample4.txt AC 24 ms
17,532 KB
system_test1.txt AC 88 ms
24,212 KB
test1.txt AC 28 ms
17,492 KB
test2.txt AC 24 ms
17,632 KB
test3.txt AC 24 ms
17,444 KB
test4.txt AC 36 ms
20,864 KB
test5.txt AC 32 ms
20,880 KB
test6.txt AC 36 ms
20,484 KB
test7.txt AC 28 ms
17,688 KB
test8.txt AC 64 ms
19,948 KB
test9.txt AC 76 ms
21,580 KB
test10.txt AC 76 ms
21,568 KB
test11.txt AC 24 ms
17,448 KB
テストケース一括ダウンロード
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.4.0-beta4-19569-03 (82f2e254)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #
using System;
using System.Collections;
using System.Collections.Generic;
 
class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		int Max=1000002;
		BIT BT=new BIT(Max);
		for(int i=0;i<N;i++){
			var d0=rs();
			int d=int.Parse(d0);
			
			if(d>0){
				int U=BT.Sum(Max)-BT.Sum(d);
				if(U<K){
					BT.Add(d+1,1);
				}
			}
			if(d<0){
				int T=BT.Sum(-d+1)-BT.Sum(-d);
				if(T>0){
					BT.Add(-d+1,-1);
				}
			}
		}
		
		Console.WriteLine(BT.Sum(Max));
		
		
		
	}
	int N;
	int K;
	public Sol(){
		var d=rsa();
		N=int.Parse(d[0]);K=int.Parse(d[1]);
	}




	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(){return Console.ReadLine().Split(' ');}
	static int[] ria(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>int.Parse(e));}
	static long[] rla(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>long.Parse(e));}
	static double[] rda(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>double.Parse(e));}
}
class BIT{
	int MM;
	int n;
	int[] bit;
	public BIT(int n_){
		n=n_;
		MM=1<<18;
		while(MM<n*4)MM<<=1;
		bit=new int[MM+1];
	}
	//1-origin!!
	public void Add(int i,int x){
		while(i<=n){
			bit[i]+=x;
			i+=(i&-i);
		}
	}
	
	// i=>sum(a_1,...,a_i)
	// i=0 -> return 0;
	public int Sum(int i){
		int s=0;
		while(i>0){
			s+=bit[i];
			i-= (i&-i);
		}
		return s;
	}
}	
0