POJ2828 Buy Tickets
/*******************************************************************************
# Author : Neo Fung
# Email : [email protected]
# Last modified: 2012-01-27 21:01
# Filename: POJ2828 Buy Tickets.cpp
# Description : , POS ,
POS , cnt [l,r)
******************************************************************************/
#ifdef _MSC_VER
#define DEBUG
#endif
#include <fstream>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <limits.h>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <functional>
#include <ctype.h>
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MAX 200010
using namespace std;
struct NODE
{
int l,r,cnt;
}node[MAX<<2];
pair<int,int> order[MAX];
int result[MAX];
void init()
{
memset(node,'\0',sizeof(node));
}
void build(const int &t , const int &l,const int &r)
{
node[t].l=l;
node[t].r=r;
node[t].cnt=r-l;
if(l==r-1)
return;
int mid=(l+r)>>1;
build(L(t),l,mid);
build(R(t),mid,r);
}
void update(const int &t,const int &pos,const int &val)
{
--node[t].cnt;
if(node[t].l == node[t].r-1)
{
result[node[t].l]=val;
return;
}
if(node[L(t)].cnt > pos)
update(L(t),pos,val);
else{
update(R(t),pos - node[L(t)].cnt,val);
}
}
int main(void)
{
#ifdef DEBUG
freopen("../stdin.txt","r",stdin);
freopen("../stdout.txt","w",stdout);
#endif
int n;
while(~scanf("%d",&n))
{
init();
build(1,0,n);
for(int i=0;i<n;++i)
scanf("%d%d",&order[i].first,&order[i].second);
for(int i=n-1;i>=0;--i)
update(1,order[i].first,order[i].second);
for(int i=0;i<n;++i)
printf("%d%c",result[i],i==(n-1)?'
':' ');
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.