set<pair<int,int> > 的运用

In this cafeteria, the N tables are all ordered in one line, where table number 1 is the closest to the window and table number N is the closest to the door.

Each time a group of X people enter the cafeteria, one of the cafeteria staff escorts the guests to the table with the smallest number of chairs greater than or equal to X chairs among all available tables. If there’s more than one such table, the guests are escorted to the table that is closest to the window. If there isn't any suitable table available, the group will leave the cafeteria immediately. A table is considered available if no one sits around it.

Eyad likes to help others and also likes to prove that he has learned something from the training of Master Hasan. Therefore, he decided to write a program that helps the cafeteria staff choose the right table for a newly arriving group.

Given the log file of who entered and who left the cafeteria, find the table at which a given group should sit.

Input

The first line of input contains two integers N and Q (1 ≤ N, Q ≤ 10⁵), the number of tables in the cafeteria and the number of events in the log file.

The second line contains N integers, each represents the size of a table (number of chairs around it). The tables are given in order from 1 to N. The size of each table is at least 1 and at most 10⁵.

Each of the following Q lines describes an event in one of the following formats:

- in X: means a group of X (1 ≤ X ≤ 10⁵) people entered the cafeteria.

- out T: means the group on table number T (1 ≤ T ≤ N) just left the cafeteria, the table is now available. It is guaranteed that a group was sitting on this table (input is valid).

Initially, all tables are empty, and the log lists the events in the same order they occurred (in chronological order).

Output

For each event of the first type, print the number of the table on which the coming group should sit. If for any event a group cannot be escorted to any table, print - 1 for that event.

Example

Input

4 7
1 2 6 7
in 4
in 1
in 3
in 5
out 1
out 4
in 7

Output

3
1　　         
4
-1

做这题之前先来普及下    set<pair<int,int> > 的用法         注意：set<pair<int,int> >;      //     最后的> >  是　　　　 >空格>   否则会报错

其次

set<pair<int,int> >在头文件<set>中，并且要加上using namespace std；

<vector> 头文件    // iterator  迭代器迭代程序

set<pair<int,int> > // 是一种类，注意：定义的时候右边的两个> >要空一格。

在头文件<set>中

set<pair<int,int> > s　　 // 声明 s s是类名，

set<pair<int,int> >::iterator it;　　　　 // iterator 迭代器迭代程序

lower_bound(key_value) 返回第一个大于等于key_value的定位器

upper_bound(key_value)，返回最后一个大于等于key_value的定位器

假若上面查找的没有符合条件的，那么他们的值等于 s.end（）

s.erase(it); 释放掉it的值

s.insert(make_pair(a[i],i)) 插入

it=s.lower_bound(make_pair(t,0));//寻找答案


ac代码：

#include<iostream>
#include<set>
#include<vector>
using namespace std;
const int maxn=1e5+10;
int n,q,a[maxn];
set<pair<int,int> > s; //最后两个> > 是 >空格> 否则会报错
set<pair<int,int> >::iterator it; // iterator 迭代器迭代程序
int main() //set默认的比较规则先按照first比较，如果first相同，再按照second 比较。
{
　　cin>>n>>q;
　　int i,x;
　　char str[10];
　　for (i=1;i<=n;i++){
　　　　cin>>a[i];
　　　　s.insert(make_pair(a[i],i)); //插入椅子数及其桌号
　　}
　　while (q--){
　　　　cin>>str>>x;
　　　　if (str[0]=='i'){
　　　　　　it=s.lower_bound(make_pair(x,0)); //lower_bound(key_value) 返回第一个大于等于key_value的定位器
　　　　　　if (it==s.end()){ //假若上面查找的没有符合条件的，那么他们的值等于 s.end（）
　　　　　　　　cout<<"-1\n";
　　　　　　　　continue;
　　　　　　}
　　　　　　else{
　　　　　　cout<<it->second<<endl;
　　　　　　s.erase(it);//释放掉了桌号，相当于标记该桌号不能再用
　　　　　　　}
　　　　}
　　　　else{
　　　　　　s.insert(make_pair(a[x],x));
　　　　}
　　}
return 0;
}

巴特西

set<pair<int,int> > 的运用

最新文章

热门文章