1004——Codeforces Round #495 (Div. 2)

http://codeforces.com/contest/1004

codeforces

2018.7.6(凌晨)参加，（ABC）
2018.7.6整理

A：
模拟

B：
推一下结论发现，直接输出0101010...

C：
线段树，枚举左端点，查询右边有多少不同的数，权值线段树。没开longlnog第一次Wa了。。。

upd：想复杂了，不需要线段树。首先就来一个变量表示有多少个不同的数num，记录每个点出现了多少次cnt[]。然后从左边开始往右扫，扫过一个点，cnt[a[i]]--，如果cnt[a[i]]==0了，说明这是最后一个a[i],往右就没有了，于是num--，然后ans+=num。

E：
思路：二分，然后判断。反正代码写的有问题。
正解：k个点一定在直径上，然后类似滑动窗口的，每次选k个点，更新答案。

A：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline LL read() { 
    LL x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int D = 1e9;
map<LL,int> p;
LL a[110];
int main () {
    LL n = read(),d = read(),ans = 0;
    for (int i=1; i<=n; ++i) {
        a[i] = read();
    }
    ans += 2;
    for (int i=1; i<n; ++i) {
        LL t1 = a[i] + d;
        LL t2 = a[i+1] - d;
        if (t1 == t2) ans++;
        else if (t1 < t2){
            ans += 2;
        }
    }
    cout << ans;
    return 0;
}

B：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read() { 
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
int main () {
    int n = read(),m = read();
    for (int i=1; i<=n; ++i) {
        if (i & 1) cout << 0;
        else cout << 1;
    }
    return 0;
}

C：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read() { 
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 500010;
int sum[N],a[N],c[N];
bool f[N];
#define Root 1,mx,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
void pushup(int rt) {
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void update(int l,int r,int rt,int p,int val) {
    if (l == r) {sum[rt] = val;return; }
    int mid = (l + r) >> 1;
    if (p <= mid) update(lson,p,val);
    else update(rson,p,val);
    pushup(rt);
}
int main () {
    int n = read(),mx = 0;
    for (int i=1; i<=n; ++i) 
        a[i] = read(),mx = max(mx,a[i]);
    for (int i=1; i<=n; ++i) {
        if (!c[a[i]]) update(Root,a[i],1);
        c[a[i]]++;
    }
    LL ans = 0;
    for (int i=1; i<=n; ++i) {
        c[a[i]] --;
        if (c[a[i]] == 0) update(Root,a[i],0);
        if (f[a[i]]) continue;
        ans += sum[1];
        f[a[i]] = true;
    }
    cout << ans;
    return 0;
}