70分,其余TLE,求调!
查看原帖
70分,其余TLE,求调!
602372
Brilliant11001楼主2023/8/26 11:18
#include <iostream>
#include <cstring> 
using namespace std;
const int N = 100010;
struct node{
	int head;
	int t;
}ship[N];
int n, e[N * 3], ne[N * 3], idx = 1;
int cnt[N]; 
node q[N];
int hh, tt = -1;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	
	for(register int i = 1; i <= n; i++) {
		int k;
		cin >> ship[i].t >> k;
		for(register int j = 1; j <= k; j++) {
			int x;
			cin >> x;
			e[idx] = x, ne[idx] = ship[i].head, ship[i].head = idx++; //插入 
		}
	}
	
	int maxx = 0, ans = 0; 
	for(register int i = 1; i <= n; i++) {
		q[++tt] = ship[i]; //入队
		while(q[hh].t <= ship[i].t - 86400) { //若队头在24小时之外则弹掉 
			//去掉弹出的国籍
			for(register int j = q[hh].head; j; j = ne[j]) {
				int k = e[j];
				cnt[k]--;
			}
			hh++;
		}
		//将新入队的国籍加上
		for(register int j = ship[i].head; j; j = ne[j]) {
			int k = e[j];
			cnt[k]++;
			maxx = max(maxx, e[j]); //记录最大的国籍 
		}
		//输出
		for(register int i = 1; i <= maxx; i++) {
			if(cnt[i] >= 1) ans++;
		} 
		cout << ans << endl;
		ans = 0;
	}
	return 0;
}

蒟蒻实在不知道怎么优化了。。。

2023/8/26 11:18
加载中...