「CF551X」Codeforces Round #307 (Div. 2)

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mod 1000000007
#define pa pair<int,int>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
int ans[2005];
struct data{
    int v,id;
}a[2005];
bool operator<(data a,data b)
{
    return a.v>b.v;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        a[i].v=read(),a[i].id=i;
    sort(a+1,a+n+1);
    int last,now=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i].v!=a[i-1].v)last=now+1;
        ans[a[i].id]=last;
        now++;
    }
    for(int i=1;i<=n;i++)
        printf("%d ",ans[i]);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define mod 1000000007

#define pa pair<int,int>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

int ans[2005];

struct data{

int v,id;

}a[2005];

bool operator<(data a,data b)

{

return a.v>b.v;

}

int main()

{

n=read();

for(int i=1;i<=n;i++)

a[i].v=read(),a[i].id=i;

sort(a+1,a+n+1);

int last,now=0;

for(int i=1;i<=n;i++)

{

if(a[i].v!=a[i-1].v)last=now+1;

ans[a[i].id]=last;

now++;

}

for(int i=1;i<=n;i++)

printf("%d ",ans[i]);

return 0;

}

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mod 1000000007
#define inf 1000000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char c[3][100005];
int t[3][27];
int mx,my;
bool cal(int x)
{
    int y=inf;
    for(int i=0;i<26;i++)
    {
        if(t[0][i]<x*t[1][i])return 0;
        if(t[2][i])y=min(y,(t[0][i]-x*t[1][i])/t[2][i]);
    }
    if(y==inf)y=0;
    if(x+y>mx+my)mx=x,my=y;
    return 1;
}
int main()
{
    scanf("%s",c[0]+1);
    scanf("%s",c[1]+1);
    scanf("%s",c[2]+1);
    for(int i=0;i<3;i++)
    {
        int len=strlen(c[i]+1);
        for(int j=1;j<=len;j++)
            t[i][c[i][j]-'a']++;
    }
    for(int i=0;;i++)if(!cal(i))break;
    for(int i=1;i<=mx;i++)printf("%s",c[1]+1);
    for(int i=1;i<=my;i++)printf("%s",c[2]+1);
    for(int i=0;i<26;i++)
        for(int j=1;j<=t[0][i]-mx*t[1][i]-my*t[2][i];j++)
            printf("%c",(char)(i+'a'));
    puts("");
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define mod 1000000007

#define inf 1000000000

#define pa pair<int,int>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

char c[3][100005];

int t[3][27];

int mx,my;

bool cal(int x)

{

int y=inf;

for(int i=0;i<26;i++)

{

if(t[0][i]<x*t[1][i])return 0;

if(t[2][i])y=min(y,(t[0][i]-x*t[1][i])/t[2][i]);

}

if(y==inf)y=0;

if(x+y>mx+my)mx=x,my=y;

return 1;

}

int main()

{

scanf("%s",c[0]+1);

scanf("%s",c[1]+1);

scanf("%s",c[2]+1);

for(int i=0;i<3;i++)

{

int len=strlen(c[i]+1);

for(int j=1;j<=len;j++)

t[i][c[i][j]-'a']++;

}

for(int i=0;;i++)if(!cal(i))break;

for(int i=1;i<=mx;i++)printf("%s",c[1]+1);

for(int i=1;i<=my;i++)printf("%s",c[2]+1);

for(int i=0;i<26;i++)

for(int j=1;j<=t[0][i]-mx*t[1][i]-my*t[2][i];j++)

printf("%c",(char)(i+'a'));

puts("");

return 0;

}

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mod 1000000007
#define inf 1000000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
int a[100005];
bool check(ll mid)
{
    ll stu=m,re=0;
    for(int i=n;i>=1;i--)
    {
        int x=a[i];
        if(re>=x){re-=x;continue;}
        else x-=re,re=0;
        if(x>0&&mid<i)return 0;
        ll t=x/(mid-i+1);
        if(x%(mid-i+1))t++;
        if(t>stu)return 0;
        stu-=t;re+=t*(mid-i+1)-x;
    }
    return 1;
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    ll l=1,r=1000000000000000LL;
    while(l<=r)
    {
        ll mid=(l+r)>>1;
        if(check(mid))r=mid-1;
        else l=mid+1;
    }
    cout<<l+1<<endl;
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define mod 1000000007

#define inf 1000000000

#define pa pair<int,int>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m;

int a[100005];

bool check(ll mid)

{

ll stu=m,re=0;

for(int i=n;i>=1;i--)

{

int x=a[i];

if(re>=x){re-=x;continue;}

else x-=re,re=0;

if(x>0&&mid<i)return 0;

ll t=x/(mid-i+1);

if(x%(mid-i+1))t++;

if(t>stu)return 0;

stu-=t;re+=t*(mid-i+1)-x;

}

return 1;

}

int main()

{

n=read();m=read();

for(int i=1;i<=n;i++)a[i]=read();

ll l=1,r=1000000000000000LL;

while(l<=r)

{

ll mid=(l+r)>>1;

if(check(mid))r=mid-1;

else l=mid+1;

}

cout<<l+1<<endl;

return 0;

}

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll bin[65];
ll n,K,l,mod;
ll qpow(ll a,ll b)
{
    ll ans=1;
    for(ll i=b;i;i>>=1,a=a*a%mod)
        if(i&1)ans=ans*a%mod;
    return ans;
}
struct M{
    ll v[2][2];
    M(){
        memset(v,0,sizeof(v));
    }
    friend M operator*(M a,M b){
        M c;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                for(int k=0;k<2;k++)
                    c.v[i][j]=(c.v[i][j]+a.v[i][k]*b.v[k][j])%mod;
        return c;
    }
    friend M operator^(M a,ll b){
        M ans;
        ans.v[0][0]=ans.v[1][1]=1;
        for(ll i=b;i;i>>=1,a=a*a)
            if(i&1)ans=ans*a;
        return ans;
    }
}b;
int main()
{
    bin[0]=1;for(int i=1;i<64;i++)bin[i]=bin[i-1]<<1;
    b.v[0][0]=b.v[0][1]=b.v[1][0]=1;
    n=read();K=read();l=read();mod=read();
    if(K>=bin[min(60LL,l)]){puts("0");return 0;}
    ll ans=1;
    for(int i=l-1;i>=0;i--)
    {
        ll t=(b^(n+1)).v[0][0];
        if(K&bin[i]&&i<=60)
            ans=ans*(qpow(2,n)-t+mod)%mod;
        else ans=ans*t%mod;
    }
    cout<<ans%mod<<endl;
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define pa pair<int,int>

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

ll bin[65];

ll n,K,l,mod;

ll qpow(ll a,ll b)

{

ll ans=1;

for(ll i=b;i;i>>=1,a=a*a%mod)

if(i&1)ans=ans*a%mod;

return ans;

}

struct M{

ll v[2][2];

M(){

memset(v,0,sizeof(v));

}

friend M operator*(M a,M b){

M c;

for(int i=0;i<2;i++)

for(int j=0;j<2;j++)

for(int k=0;k<2;k++)

c.v[i][j]=(c.v[i][j]+a.v[i][k]*b.v[k][j])%mod;

return c;

}

friend M operator^(M a,ll b){

M ans;

ans.v[0][0]=ans.v[1][1]=1;

for(ll i=b;i;i>>=1,a=a*a)

if(i&1)ans=ans*a;

return ans;

}

}b;

int main()

{

bin[0]=1;for(int i=1;i<64;i++)bin[i]=bin[i-1]<<1;

b.v[0][0]=b.v[0][1]=b.v[1][0]=1;

n=read();K=read();l=read();mod=read();

if(K>=bin[min(60LL,l)]){puts("0");return 0;}

ll ans=1;

for(int i=l-1;i>=0;i--)

{

ll t=(b^(n+1)).v[0][0];

if(K&bin[i]&&i<=60)

ans=ans*(qpow(2,n)-t+mod)%mod;

else ans=ans*t%mod;

}

cout<<ans%mod<<endl;

return 0;

}

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m=1000,c,q,mn,mx;
ll a[500005],tag[505];
int pos[500005],lp[505],rp[505];
vector<pair<ll,int> >b[505];
void rebuild(int x)
{
    b[x].clear();
    for(int i=lp[x];i<=rp[x];i++)
    {
        a[i]+=tag[x];
        b[x].push_back(make_pair(a[i],i));
    }
    sort(b[x].begin(),b[x].end());
    tag[x]=0;
}
void query(int x,ll val)
{
    val-=tag[x];
    pair<ll,int>t1,t2;
    if(lower_bound(b[x].begin(),b[x].end(),make_pair(val,0))!=b[x].end())
    {
        t1=*lower_bound(b[x].begin(),b[x].end(),make_pair(val,0));
        if(t1.first==val)
            mn=min(mn,t1.second);
    }
    if(lower_bound(b[x].begin(),b[x].end(),make_pair(val+1,0))!=b[x].begin())
    {
        t2=*--lower_bound(b[x].begin(),b[x].end(),make_pair(val+1,0));
        if(t2.first==val)
            mx=max(mx,t2.second);
    }
}
void add()
{
    int l=read(),r=read(),x=read(),L=pos[l],R=pos[r];
    if(L==R)
        for(int i=l;i<=r;i++)a[i]+=x;
    else 
    {
        for(int i=l;i<=rp[L];i++)a[i]+=x;
        for(int i=lp[R];i<=r;i++)a[i]+=x;
        for(int i=L+1;i<R;i++)tag[i]+=x;
    }
    rebuild(L);
    if(L!=R)rebuild(R);
}
void query()
{
    int x=read();
    mx=-inf;mn=inf;
    for(int i=1;i<=c;i++)query(i,x);
    if(mn==inf)puts("-1");
    else printf("%d\n",mx-mn);
}
int main()
{
    n=read();q=read();c=n/1000+(n%1000!=0);
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)pos[i]=(i-1)/1000+1;
    lp[1]=1;rp[1]=1000;
    for(int i=2;i<=c;i++)lp[i]=lp[i-1]+1000,rp[i]=rp[i-1]+1000;
    rp[c]=n;
    for(int i=1;i<=c;i++)rebuild(i);
    while(q--)
    {
        int f=read();
        if(f==1)add();
        else query();
    }
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define pa pair<int,int>

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m=1000,c,q,mn,mx;

ll a[500005],tag[505];

int pos[500005],lp[505],rp[505];

vector<pair<ll,int> >b[505];

void rebuild(int x)

{

b[x].clear();

for(int i=lp[x];i<=rp[x];i++)

{

a[i]+=tag[x];

b[x].push_back(make_pair(a[i],i));

}

sort(b[x].begin(),b[x].end());

tag[x]=0;

}

void query(int x,ll val)

{

val-=tag[x];

pair<ll,int>t1,t2;

if(lower_bound(b[x].begin(),b[x].end(),make_pair(val,0))!=b[x].end())

{

t1=*lower_bound(b[x].begin(),b[x].end(),make_pair(val,0));

if(t1.first==val)

mn=min(mn,t1.second);

}

if(lower_bound(b[x].begin(),b[x].end(),make_pair(val+1,0))!=b[x].begin())

{

t2=*--lower_bound(b[x].begin(),b[x].end(),make_pair(val+1,0));

if(t2.first==val)

mx=max(mx,t2.second);

}

void add()

{

int l=read(),r=read(),x=read(),L=pos[l],R=pos[r];

if(L==R)

for(int i=l;i<=r;i++)a[i]+=x;

else

{

for(int i=l;i<=rp[L];i++)a[i]+=x;

for(int i=lp[R];i<=r;i++)a[i]+=x;

for(int i=L+1;i<R;i++)tag[i]+=x;

}

rebuild(L);

if(L!=R)rebuild(R);

}

void query()

{

int x=read();

mx=-inf;mn=inf;

for(int i=1;i<=c;i++)query(i,x);

if(mn==inf)puts("-1");

else printf("%d\n",mx-mn);

}

int main()

{

n=read();q=read();c=n/1000+(n%1000!=0);

for(int i=1;i<=n;i++)a[i]=read();

for(int i=1;i<=n;i++)pos[i]=(i-1)/1000+1;

lp[1]=1;rp[1]=1000;

for(int i=2;i<=c;i++)lp[i]=lp[i-1]+1000,rp[i]=rp[i-1]+1000;

rp[c]=n;

for(int i=1;i<=c;i++)rebuild(i);

while(q--)

{

int f=read();

if(f==1)add();

else query();

}

return 0;

}

hzwer.com _ Home | http://hzwer.com

分类目录

热门文章

Myfriends

近期评论