求助,最后一个点没有过!

P3586 [POI2015] LOG

starseven @ 2020-09-02 12:25:39

#include<cstdio>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define Starseven main
#define ll long long
#define lowbit(x) (x & (-x))
namespace lyt {
    void read(int &x){
    char ch=getchar();int re=0,op=1;
    while(ch<'0'||ch>'9'){if(ch=='-') op=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){re=(re<<3)+(re<<1)+ch-'0';ch=getchar();}
    x = re * op;
    return ;
    }
    void read(long long &x){
    char ch=getchar();long long re=0,op=1;
    while(ch<'0'||ch>'9'){if(ch=='-') op=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){re=(re<<3ll)+(re<<1ll)+ch-'0';ch=getchar();}
    x = re * op;
    return ;
    }
    void write(int x){
        if(x<0){putchar('-');x=-x;}
        if(x>9) write(x/10);
        putchar(x%10+'0');
        return ;
    }//记得自己加空格和换行 
    void write(long long x){
        if(x<0){putchar('-');x=-x;}
        if(x>9) write(x/10);
        putchar(x%10+'0');
        return ;
    }//记得自己加空格和换行
    int max(int x,int y){return x<y?y:x;}
    int min(int x,int y){return x<y?x:y;}
    int abs(int x){return x<0?-x:x;}
    long long max(long long x,long long y){return x<y?y:x;}
    long long min(long long x,long long y){return x<y?x:y;}
    long long abs(long long x){return x<0?-x:x;}
    double max(double x,double y){return x<y?y:x;}
    double min(double x,double y){return x<y?x:y;}
    double abs(double x){return x<0?-x:x;}
    void swap(int &a,int &b) {a ^= b ^= a ^= b;}
    void swap(long long &a,long long &b) {a ^= b ^= a ^= b;}
    ll Power(ll a, ll b, ll p) {
        ll re = 1;
        while(b) {
            if(b & 1ll) re = (re * a) % p;
            b >>= 1ll;
            a = (a * a) % p; 
        }
        return re;
    }
    int Power(int a, int b, int p) {
        int re = 1;
        while(b) {
            if(b & 1) re = 1ll * re * a % p;
            b >>= 1;
            a = 1ll * a * a % p; 
        }
        return re;
    }
}using namespace lyt;
const int N = 8e6 + 20;
ll n, m, num, cas[N];
ll list[N], c[N], s[N], t[N];
ll tr[N][2];

void Insert(ll x, ll opt, ll k) {
    for (ll i = x; i <= num; i += lowbit(i)) tr[i][opt] += k;
}

ll Find(ll x, ll opt) {
    int re = 0;
    for (ll i = x; i; i -= lowbit(i)) re += tr[i][opt];
    return re;
}

int Starseven(void) {
    read(n);
    read(m);
    t[++num] = 0;
    for (ll i = 1; i <= m; i++) {
        char ch[5];
        scanf("%s", ch);
        read(c[i]);read(s[i]);
        t[++num] = s[i];
        if(ch[0] == 'U') cas[i] = 0;
        else cas[i] = 1;
    }
    std::sort(t + 1, t + 1 + num);
    num = std::unique(t + 1, t + 1 + num) - t - 1;
    for (ll i = 1; i <= m; i++) {
        s[i] = std::lower_bound(t + 1, t + 1 + num, s[i]) - t;
        if(cas[i] == 0ll) {
            ll x = list[c[i]];
            if(x != 0ll) {
                Insert(x, 0ll, -1ll);
                Insert(x, 1ll, -t[x]);
            }
            x = list[c[i]] = s[i];
            Insert(x, 0ll, 1ll);
            Insert(x, 1ll, t[x]);
        }
        else {
            ll x = Find(num, 0ll) - Find(s[i] - 1, 0ll);
            ll sum = s[i] ? Find(s[i] - 1, 1ll) : 0ll;
            puts(sum >= 1ll * (c[i] - x) * 1ll * t[s[i]] ? "TAK" : "NIE");
        }
    }
    return 0;   
}

我用的离线+离散化+树状数组,最后一个点错了,其他全对,求助!


by starseven @ 2020-09-02 14:20:43

现在已过, 需要在树状数组Find函数里re开long long


|