题解 - Vijos

0

是我语文不及格吗?为什么我看不懂题啊?

哪位大牛能解释一下题意?

0

cx24 LV 6 @ 16 年前

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：18ms

用点树（线段树简化版）同程序提交3次AC，LORA

顺便，第一次70第二次90

再顺便，我用Writeln的

最后顺便，本来想试试能不能一次AC的

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 56ms

├ 测试数据 08：答案正确... 41ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 88ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：185ms

树状数组WA了两次（丢脸，写错了）

之后同程序两次AC，LORA，同样是WRITELN，第一次是80

明显点树比树状数组快！

不然就是我树状数组写太丑了

0

Orz教主_Kyd LV 7 @ 16 年前

2楼居然也是教主后援团的你好你好行贿行贿

0

DFS LV 8 @ 16 年前

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 41ms

├ 测试数据 10：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：82ms

开始以为遇上了诡异问题

最后发现一直是用的write来输出

最后加上一个writeln就好了。

0

Fengyunfly LV 8 @ 16 年前

原来要write..

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

0

wasyyyy LV 3 @ 16 年前

同一个程序提交3次3个结果

第一次40分，后6个点TLE

第二次和第三次都70分，随机TLE3个点

汗。。通过去的27个人是哪台测的？

0

122 LV 3 @ 16 年前

2008-9-16 17:40:01 )

0

330459659 LV 10 @ 16 年前

var

i,j,k,n,m,v:longint;

a,b,c,e:array[0..100000]of longint;

d:array[0..100000,0..100000]of boolean;

begin

readln(n,m);

fillchar(d,sizeof(d),false);

v:=1;

for i:=1 to m do

begin

read(a[i],b[i],c[i]);

if a[i]=1

then d[b[i],c[i]]:=true

else begin

for j:=1 to c[i] do

if d[b[j],c[j]]

then if ((b[i]=b[j]))or((c[i]>=b[j])and(c[i]

0

pzy3303 LV 10 @ 16 年前

太经典了write=AC

0

swxadqecz LV 5 @ 16 年前

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

同样的机器，在无数次提交后~AC！

WRITELN也能过

0

yby.barty LV 9 @ 16 年前

只有Lora Temper能AC…………………………

0

AlNo3 LV 9 @ 16 年前

1、用write

2、Lora Temper

3、看一点RP

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

0

w卡e丹s裘t LV 6 @ 16 年前

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

Lora~~~总算跑过了!!!

0

xindi LV 3 @ 16 年前

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：25ms

with Lora Temper

AC的代价是降低2个百分点~~~

0

欧阳德 LV 4 @ 16 年前

ORZ fjxmlhx

0

5568478001 LV 3 @ 16 年前

我是盲人！！！！！请说普通话！！汉语！！

0

失落只为你 LV 3 @ 16 年前

伟大的write!!!!!!!

伟大的write!!!!!!!

伟大的write!!!!!!!

伟大的write!!!!!!!

伟大的write!!!!!!!

伟大的write!!!!!!!

伟大的write!!!!!!!

和评测机没有关系的，我在dolphin都ac

来自： fjxmlhx

在l处添加一个左括号，在r处添加一个右括号。

ans=1~r的左括号-1~l-1的右括号

( 2008-9-15 7:48:42 )

就这么做，我用线段树写的，不过ac不能。

本机cena测ac共0.87s,最慢点0.15s，vj上交10次同样程序，80-70-50-80-60-70-80-80-70-70，全TLE

另外查纪录发现：puppy上1人ac,lora上1人，其余9人ac全是tiger上的。。。

另：本题已经成为VJ通过率第2低的题了，截至08.9.15。

另：本机测试n=m=500000数据，1s内出解，我没什么好说得了。

另：经过试验，即使将答案存在数组里最后一起输出也ac不能。

最后给个很重要建议：（puppy victoria一样，dolphin更差，Lora Temper好一点）

没

遇

到

T

i

g

e

r

就

别

交

了

！

以上纯属废话。。。提交10几次后终于AC with dolphin（？！）。。。令人难以置信，dolphin居然完成了puppy lora...没有完成的任务。

原因在于：

伟大的write!!!!!!

伟大的write!!!!!!!

0

牧云海 LV 10 @ 15 年前

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

使用write的线段树

-1

张松炜山东 LV 8 @ 6 年前

#include<iostream>
#include<cstdio>
using namespace std;
int c1[200005];
int c2[200005];
int n,m;
int lowbit(int x)
{
return x&(-x);
}
void addx(int x,int v)
{
while(x<=n)
{
c1[x]+=v;
x+=lowbit(x);
}
}
void addy(int x,int v)
{
while(x<=n)
{
c2[x]+=v;
x+=lowbit(x);
}
}
int sumx(int x)
{
int res=0;
while(x>0)
{
res+=c1[x];
x-=lowbit(x);
}
return res;
}
int sumy(int x)
{
int res=0;
while(x>0)
{
res+=c2[x];
x-=lowbit(x);
}
return res;
}
int main()
{

cin>>n>>m;
int p,q,t;
for(int i=1;i<=m;i++)
{
cin>>t>>p>>q;
if(t==1)
{
addx(p,1);
addy(q,1);
}
if(t==2)
{
cout<<sumx(q)-sumy(p-1)<<endl;
}
}
return 0;//树状数组模板题
}

-1

q234rty LV 10 @ 7 年前

容易发现答案为 $\sum_{i} [l_i \le r]-[r_i < l]$ ，树状数组记录 $\leq k$ 的 $l_i$ 和 $r_i$ 的个数即可。

#include <bits/stdc++.h>
using namespace std;
const int MAXSIZE=30000020;
int bufpos;
char buf[MAXSIZE];
void init(){
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=(buf[bufpos]=='-'))?1:0;
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
struct bit{
    int n;
    int a[50002];
    void add(int p,int v){
        for(;p<=n;p+=p&-p)
            a[p]+=v;
    }
    int query(int p){
        int ans=0;
        for(;p;p-=p&-p)
            ans+=a[p];
        return ans;
    }
}bl,br;
int main(){
    init();
    bl.n=br.n=readint();
    int m=readint();
    while(m--){
        int k=readint(),l=readint(),r=readint();
        if (k==1)
            bl.add(r,1),br.add(l,1);
        else printf("%d\n",br.query(r)-bl.query(l-1));
    }
}

题解

136 条题解

校门外的树

信息

状态

开发

支持

题解

136 条题解

校门外的树

信息

状态

开发

支持

还没有账户？

登录