Codeforces gym 101350F 아이디어
3370 단어 생각
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
When the monkey professor leaves his class for a short time, all the monkeys go bananas. N monkeys are lined up sitting side by side on their chairs. They each have the same joke book. Before the professor returns, M jokes were heard.
Each of the M jokes are said in the order given and have the following properties:
xi - position of the monkey who said it.
li – index of the joke in the book.
ki – volume the monkey says that joke.
When the monkey at position xi says the joke li, all monkeys at a distance less than or equal to ki from that monkey (including the monkey who said the joke) will fall off their chairs in laughter if they have never heard the joke li before.
If the joke li has been heard anytime during the past before, and the monkey hears it again, then he will sit back up in his chair.
A monkey can fall off his chair more than once (every time he hears a new joke), and if he is already on the ground and hears a new joke, he will stay on the ground.
Can you figure out how many monkeys will be in their seats by the time the professor comes back?
Input
The first line of input is T – the number of test cases.
The first line of each test case is N, M (1 ≤ N ≤ 105) (1 ≤ M ≤ 105) – the number of monkeys in the class, and the number of jokes said before the professor returns.
The next M lines contain the description of each joke: xi, li, ki (1 ≤ xi ≤ N) (1 ≤ li ≤ 105) (0 ≤ ki ≤ N).
Output
For each test case, output on a line a single integer - the number of monkeys in their seats after all jokes have been said.
Example
input
1
10 7
3 11 0
3 11 2
5 12 1
8 13 2
7 11 2
10 12 1
9 12 0
output
3
원숭이 n마리
모든 우스갯소리가 하는 원숭이의 번호 우스갯소리의 번호 전파 반경
우스갯소리가 지금에 퍼지면 원숭이가 들으면 땅에 웃어요. 그렇지 않으면 나무에 올라갈 거예요.
마지막에 원숭이 몇 마리가 나무 위에 있냐고 물어보셨어요.
문제풀이: 먼저 모든 라인을 처리한 다음에 현재의 원숭이에게 영향을 미치는 우스갯소리를 찾아내고 마지막으로 그가 이 우스갯소리를 들은 횟수를 찾아낸다.
#include
#include
#include
#include
#include
#include
using namespace std;
int num[100005],cnt;
struct node{
int x,y,nu,lab;
}e[100005];
vectorsp[100005];
struct nodes{
int num,lab;
bool operator sd;
set::iterator it;
int main(){
int t;
scanf("%d",&t);
while(t--){
int n,m,i,j,x,y,z;
scanf("%d%d",&n,&m);
memset(num,0,sizeof(num));
sd.clear();
for(i=1;i<=n;i++)sp[i].clear();
for(i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
e[i].lab=i;
e[i].nu=y;
e[i].x=max(1,x-z);
e[i].y=min(n,x+z);
sp[e[i].x].push_back(i);
sp[e[i].y+1].push_back(-i);
}
int ans=0;
for(i=1;i<=n;i++){
for(j=0;j0){
num[e[sp[i][j]].nu]++;
sd.insert((nodes){e[sp[i][j]].nu,e[sp[i][j]].lab});
}
else{
num[e[-sp[i][j]].nu]--;
sd.erase((nodes){e[-sp[i][j]].nu,e[-sp[i][j]].lab});
}
}
if(sd.empty())ans++;
else{
it=sd.end();
it--;
if(num[(*it).num]!=1)ans++;
}
}
printf("%d
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
11050 : 이항 계수 1이항계수를 구하는 문제. 팩토리얼 구현 후 이항계수 계산. 재귀 따윈 필요가 없다. -> alphago92님의 소스...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.