| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 257344 |
2020-08-04T06:34:39 Z |
문홍윤(#5062) |
None (JOI16_worst_reporter2) |
C++17 |
|
4 ms |
4992 KB |
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
#define lb(x, v) lower_bound(x.begin(), x.end(), v)
using namespace std;
typedef long long LL;
const int inf=1e8;
struct LAZY_SEGMENT_TREE{
int x;
struct NODE{
int st, fin;
int minn, lazy;
}tree[1600000];
void init(int point, int num){
if(num==1)tree[point].st=tree[point].fin=++x;
if(num<=1)return;
init(point*2, num-num/2);
init(point*2+1, num/2);
tree[point].st=tree[point*2].st;
tree[point].fin=tree[point*2+1].fin;
}
void eat(int point){
tree[point].minn=min(tree[point*2].minn+tree[point*2].lazy, tree[point*2+1].minn+tree[point*2+1].lazy);
}
void propogate(int point){
if(tree[point].st==tree[point].fin){
tree[point].minn+=tree[point].lazy;
tree[point].lazy=0;
return;
}
tree[point].minn+=tree[point].lazy;
tree[point*2].lazy+=tree[point].lazy;
tree[point*2+1].lazy+=tree[point].lazy;
tree[point].lazy=0;
}
void alter(int point, int a, int b, LL qu){
if(tree[point].st>=a&&tree[point].fin<=b){
tree[point].lazy+=qu;
return;
}
if(tree[point].st>b||tree[point].fin<a)return;
propogate(point);
alter(point*2, a, b, qu);
alter(point*2+1, a, b, qu);
eat(point);
}
int query(int point, int a, int b){
if(tree[point].st>=a&&tree[point].fin<=b)return tree[point].minn+tree[point].lazy;
if(tree[point].st>b||tree[point].fin<a)return inf;
propogate(point);
int ret=min(query(point*2, a, b), query(point*2+1, a, b));
eat(point);
return ret;
}
void init(int num){init(1, num);}
void alter(int a, int b, int qu){alter(1, a, b, qu);}
int query(int a, int b){return query(1, a, b);}
}seg;
int n, ans;
int arra[200010], xa[200010];
int arrb[200010], xb[200010];
vector<int> id, stk[200010];
int main(){
scanf("%d", &n);
seg.init(2*n);
for(int i=1; i<=n; i++){
scanf("%d %d", &arra[i], &xa[i]);
xa[i]*=2;
id.eb(xa[i]);
}
for(int i=1; i<=n; i++){
scanf("%d %d", &arrb[i], &xb[i]);
xb[i]*=2;
xb[i]++;
id.eb(xb[i]);
}
reverse(arra+1, arra+n+1);
reverse(arrb+1, arrb+n+1);
reverse(xa+1, xa+n+1);
reverse(xb+1, xb+n+1);
svec(id); press(id);
for(int i=1; i<=n; i++){
xa[i]=lb(id, xa[i])-id.begin()+1;
xb[i]=lb(id, xb[i])-id.begin()+1;
seg.alter(xa[i], xb[i], 1);
}
int pv=1;
ans=n;
for(int i=1; i<=n; i++){
for(; pv<=n; pv++){
if(xa[pv]>xb[i])break;
stk[arra[pv]].eb(xa[pv]);
}
if(stk[arrb[i]].size()==0)continue;
if(seg.query(stk[arrb[i]].back(), xb[i])>=1){
seg.alter(stk[arrb[i]].back(), xb[i], -1);
stk[arrb[i]].pop_back();
ans--;
}
}
printf("%d", ans);
}
/*
3
3 500
2 200
1 100
1 1000
3 700
3 400
3
3 3
3 2
1 1
3 4
3 2
1 1
6
1 70
4 50
1 30
2 20
1 10
3 0
6 100
2 90
1 80
2 60
4 40
1 10
*/
Compilation message
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
worst_reporter2.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &arra[i], &xa[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &arrb[i], &xb[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4992 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4992 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4992 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4992 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
