HZU ACM 7-7 安排座位
作者:
万俟怀烟
,
2023-03-23 18:32:56
,
所有人可见
,
阅读 149
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int cnt[N], lt[N];
struct Table {
int cnt, id;
bool operator < (const Table& t) const {
if(cnt != t.cnt) return cnt < t.cnt;
if(id != t.id) return id < t.id;
}
}table[N];
struct Order {
int number, s, t, id;
bool operator < (const Order& t) const {
if(s != t.s) return s < t.s;
if(id != t.id) return id < t.id;
}
}order[N];
int main()
{
int n, m, k = 0;
cin >> n >> m;
for(int i = 1; i <= n; i ++ )
{
int cnt;
cin >> cnt;
table[k] = {cnt, k + 1};
k ++;
}
sort(table, table + k);
// for(int i = 0; i < k; i ++ ) cout << table[i].cnt << " " << table[i].id << endl;
k = 0;
while(m --)
{
int number, s, t;
cin >> number >> s >> t;
order[k] = {number, s, t, k + 1};
k ++;
}
sort(order, order + k);
// for(int i = 0; i < k; i ++ ) cout << order[i].number << " " << order[i].s << " " << order[i].id << endl;
for(int i = 0; i < k; i ++ )
{
int num = order[i].number;
int l = 0, r = n - 1;
while(l < r)
{
int mid = (l + r) >> 1;
if(table[mid].cnt >= num) r = mid;
else l = mid + 1;
}
if(order[i].s - lt[r] >= 0)
{
lt[r] = order[i].t + order[i].s;
cout << table[r].id << endl;
}
else
{
while(order[i].s - lt[r] < 0 && r <= n - 1) r ++;
if(r == n) cout << "-1" << endl;
else
{
lt[r] = order[i].t + order[i].s;
cout << table[r].id << endl;
}
}
}
return 0;
}