oj.uz

답안 #638257

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
638257 2022-09-05T06:25:18 Z jamezzz 디지털 회로 (IOI22_circuit) C++17
18 / 100
 1044 ms 8108 KB 
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define maxn 100005
#define mod 1000002022

struct node{
	int s,e,m,v,lz;
	node *l,*r;
	node(int _s,int _e){
		s=_s;e=_e;m=(s+e)>>1;v=0;lz=0;
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	void ppo(){
		if(lz)v=(e-s+1)-v;
		if(s!=e){
			l->lz^=lz;
			r->lz^=lz;
		}
		lz=0;
	}
	void set(int x,int nv){
		if(s==x&&e==x){v=nv;return;}
		if(x<=m)l->set(x,nv);
		else r->set(x,nv);
		l->ppo(),r->ppo();
		v=l->v+r->v;
	}
	void flip(int x,int y){
		if(s==x&&e==y){lz^=1;return;}
		if(y<=m)l->flip(x,y);
		else if(x>m)r->flip(x,y);
		else l->flip(x,m),r->flip(m+1,y);
		l->ppo(),r->ppo();
		v=l->v+r->v;
	}
	int qry(int x,int y){
		ppo();
		if(s==x&&e==y)return v;
		if(y<=m)return l->qry(x,y);
		if(x>m)return r->qry(x,y);
		return l->qry(x,m)+r->qry(m+1,y);
	}
}*root;

int n,m;
ll mult;

ll fpow(int a,int x){
	if(x==0)return 1;
	ll t=fpow(a,x/2);
	ll r=(t*t)%mod;
	if(x%2)r=(r*a)%mod;
	return r;
}

void init(int N,int M,vector<int> P,vector<int> A){
	n=N,m=M;
	int tmp=n+1,lg2=0;
	while(tmp!=1)++lg2,tmp/=2;
	mult=fpow(2,n-lg2);
	root=new node(0,M-1);
	for(int i=0;i<M;++i)root->set(i,A[i]);
}

int count_ways(int L,int R){
	root->flip(L-n,R-n);
	return (int)((mult*root->qry(0,m-1))%mod);
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '422083442'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '422083442'
15 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 640 ms 4148 KB Output is correct
2 Correct 771 ms 7960 KB Output is correct
3 Correct 925 ms 8108 KB Output is correct
4 Correct 771 ms 7972 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 640 ms 4148 KB Output is correct
2 Correct 771 ms 7960 KB Output is correct
3 Correct 925 ms 8108 KB Output is correct
4 Correct 771 ms 7972 KB Output is correct
5 Correct 644 ms 4132 KB Output is correct
6 Correct 1020 ms 8000 KB Output is correct
7 Correct 1044 ms 7960 KB Output is correct
8 Correct 741 ms 7996 KB Output is correct
9 Correct 553 ms 464 KB Output is correct
10 Correct 834 ms 720 KB Output is correct
11 Correct 981 ms 720 KB Output is correct
12 Correct 869 ms 720 KB Output is correct

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '422083442'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '422083442'
15 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '422083442'
15 Halted 0 ms 0 KB -