Submission #61826112

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
Start: 
End: 
Time used: 
「責任を負う人の話は、あなたと話したことがありますよね」 
「当時の私はまだわからないけど……今は理解できるようになった」 
「大人としての責務。そして、その延長線上にある、あなたの選択」 
「それに代表されるアイデアもあります」 
「だから、先生」 
「信じられる大人のあなたなら、この歪んだ変形の終点とは、違う結果……そこにつながる選択肢……きっとあなたは見つけることができます」
DON'T GET STUCK ON ONE APPROACH!!!
*/
#include <bits/stdc++.h>//喵内～
#define re register//喵内～
#define rep(i,a,b) for (re int i = (a);i <= (b); ++i)
#define debug(x) cout << #x << '=',print(x),putchar(' ')
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define pi pair<int,int>
#define mp(a,b) make_pair(a,b)
typedef long long ll;
using namespace std;//喵内～
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

/*
Start: 
End: 
Time used: 
「責任を負う人の話は、あなたと話したことがありますよね」 
「当時の私はまだわからないけど……今は理解できるようになった」 
「大人としての責務。そして、その延長線上にある、あなたの選択」 
「それに代表されるアイデアもあります」 
「だから、先生」 
「信じられる大人のあなたなら、この歪んだ変形の終点とは、違う結果……そこにつながる選択肢……きっとあなたは見つけることができます」
DON'T GET STUCK ON ONE APPROACH!!!
*/
#include <bits/stdc++.h>//喵内～
#define re register//喵内～
#define rep(i,a,b) for (re int i = (a);i <= (b); ++i)
#define debug(x) cout << #x << '=',print(x),putchar(' ')
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define pi pair<int,int>
#define mp(a,b) make_pair(a,b)
typedef long long ll;
using namespace std;//喵内～
inline ll read(){
    ll s = 0,f = 1;char c = getchar();
    while (!isdigit(c)){if (c == '-')f = -1;c = getchar();}
    while (isdigit(c)){s = (s<<3) + (s<<1) + (c ^ 48);c = getchar();}
    return s * f;
}//喵内～
void print(__int128 x){if (x < 0) {putchar('-'),print(-x);return ;}if (x >= 10) print(x / 10);putchar(x % 10 + 48);}//喵内～
const int Mod = 1e9 + 7;//喵内～要填数字哟～
//const int Mod = 998244353;//喵内～要填数字哟～
const ll INF = 0x3f3f3f3f;
const int N = 5e5 + 5;//喵内～要填数字哟～
ll qpow(ll x,ll y){
   ll res = 1;
    for (;y;y >>= 1,x = x * x % Mod) if (y & 1) res = res * x % Mod;
    return res;
}
int n;
int tree[N << 2],lazy[N << 2];
void pushup(int rt){tree[rt] = max(tree[rt << 1],tree[rt << 1 | 1]);}
void build(int rt,int l,int r){
    if (l == r){tree[rt] = l; return ;}
    int mid = l + r >> 1;
    build(rt << 1,l,mid);
    build(rt << 1 | 1,mid + 1,r);
    pushup(rt);
}
void pushdown(int rt){
    if (lazy[rt]){
        lazy[rt << 1] += lazy[rt];
        lazy[rt << 1 | 1] += lazy[rt];
        tree[rt << 1] += lazy[rt];
        tree[rt << 1 | 1] += lazy[rt];
        lazy[rt] = 0;
    }
}
void add(int rt,int l,int r,int x,int y,int val){
    if (l > y || r < x) return ;
    if (l >= x && r <= y){
        tree[rt] += val;
        lazy[rt] += val;
        return ;
    }
    pushdown(rt);
    int mid = l + r >> 1;
    add(rt << 1,l,mid,x,y,val);
    add(rt << 1 | 1,mid + 1,r,x,y,val);
    pushup(rt);
}
int rfind(int rt,int l,int r,int x){
    if (l == r) return l;
    pushdown(rt);
    int mid = l + r >> 1;
    if (tree[rt << 1] > x) return rfind(rt << 1,l,mid,x);
    else return rfind(rt << 1 | 1,mid + 1,r,x);
}
int query(int rt,int l,int r,int pos){
    if (l == r) return tree[rt];
    int mid = l + r >> 1;
    pushdown(rt);
    if (pos <= mid) return query(rt << 1,l,mid,pos);
    else return query(rt << 1 | 1,mid + 1,r,pos);
}
signed main(){
    n = read();
    build(1,1,N - 1);
    for (int i = 1;i <= n;++i){
        int l = read(),r = read();
        int L = rfind(1,1,N - 1,l - 1),R = rfind(1,1,N - 1,r) - 1;
        if (L > R) continue;
        add(1,1,N - 1,L,R,1);
    }

    int q = read();
    while (q--){
        int x = read();
        cout << query(1,1,N - 1,x) << endl;
    }
    return 0;
}//喵内～
/*
What's wrong with my code?
1. 小数据？特殊数据？如 n = 1?
2. 最小值，最大值取多少？是否会溢出？
3. 初始值有没有赋值？有没有建树？
4. 数组大小？是否越界？
5. 思考暴力的时候，考虑是否可能是多个连续段？或者是个数不确定无法暴力？
6. 进行详细的分类讨论?
7. 选择的区间是否可以为空？

Trick:
1. 连通 通常带有特殊性质
2. LIS 有另一种求法
3. Brovuka?

About implementation skills:
1. 全局变量多用长变量名，而局部变量，临时变量，和函数传递的参数使用短变量名。
2. 大模拟尽量遵循：怎么方便怎么写。
3. 对于一些数据很小的需要维护的量并且需要大量讨论时，可以考虑把数组拆掉换成变量。
4. 写成多个函数。
*/

Submission Info

Compile Error

Main.cpp: In function ‘void build(int, int, int)’:
Main.cpp:43:17: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   43 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function ‘void add(int, int, int, int, int, int)’:
Main.cpp:65:17: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   65 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function ‘int rfind(int, int, int, int)’:
Main.cpp:73:17: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   73 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function ‘int query(int, int, int, int)’:
Main.cpp:79:17: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   79 |     int mid = l + r >> 1;
      |               ~~^~~

Judge Result