资格赛C

题目描述

美团点评上有很多餐馆优惠券，用户可以在美团点评App上购买。每种优惠券有一个唯一的正整数编号。每个人可以拥有多张优惠券，但每种优惠券只能同时拥有至多一张。每种优惠券可以在使用之后继续购买。

当用户在相应餐馆就餐时，可以在餐馆使用优惠券进行消费。某人优惠券的购买和使用按照时间顺序逐行记录在一个日志文件中，运营人员会定期抽查日志文件看业务是否正确。业务正确的定义为：一个优惠券必须先被购买，然后才能被使用。

某次抽查时，发现有硬盘故障，历史日志中有部分行损坏，这些行的存在是已知的，但是行的内容读不出来。假设损坏的行可以是任意的优惠券的购买或者使用。

现在给一个日志文件，问这个日志文件是否正确。若有错，输出最早出现错误的那一行，即求出最大s，使得记录1到s-1满足要求；若没有错误，输出-1。

输入描述:

输入包含多组数据

m 分别表示 m (1 ≤ m ≤ 5 * 10^5) 条记录。

下面有m行，格式为：

I x （I为Input的缩写，表示购买优惠券x）；

O x（O为Output的缩写，表示使用优惠券x）；

? （表示这条记录不知道）。

这里x为正整数，且x ≤ 10^5 。

输出描述:

-1 或 x(1 ≤ x ≤ m) 其中x为使得1到x-1这些记录合法的最大行号。

输入例子:

0
1
O 1
2
?
O 1
3
I 1
?
O 1
2
I 2
O 1

输出例子:

-1
1
-1
-1
2

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 
 5 int b[500005];
 6 int c[500005];
 7 set<int >sum;
 8 set<int >::iterator it;
 9 
10 int main(){
11     int n;
12     while(scanf("%d",&n)!=EOF){
13          if(n==0) {
14             printf("-1
");continue;
15         }
16         char s[10];int x;
17         int l=0;
18         int t=0,tt=0;
19         sum.clear();
20         memset(b,0,sizeof(b));
21         memset(c,0,sizeof(c));
22         int y;
23         for(int i=1;i<=n;i++){
24             scanf("%s",s);
25             if(s[0]=='?') sum.insert(i);
26             else {
27                 scanf("%d",&x);
28                 if(tt) continue;
29                 if(s[0]=='I'){
30                     if(b[x]==0) b[x]=i;
31                     else {
32                             t=0;
33                         it=sum.lower_bound(b[x]);
34                         if(it!=sum.end()) {
35                              sum.erase(*it);b[x]=i;t=1;
36                             }
37                         if(t==0) {y=i;tt=1;}
38                     }
39                 }
40                 else {
41                     if(b[x]) {
42                     b[x]=0;   
43                   }
44                     else {
45                         t=0;
46                         it=sum.lower_bound(c[x]);
47                         if(it!=sum.end()) {
48                             sum.erase(*it);t=1;
49                         }
50                         if(t==0) {y=i;tt=1;}
51                    }
52                  c[x]=i;
53                 }
54             }
55         }
56         if(tt==0){
57             printf("-1
");
58         }
59         else printf("%d
",y);
60     }
61     return 0;
62 }