oj.uz

Submission #218497

# Submission time Handle Problem Language Result Execution time Memory
218497 2020-04-02T08:28:24 Z patrikpavic2 Long Mansion (JOI17_long_mansion) C++17
5 / 100
 3000 ms 16504 KB 
#include <cstdio>
#include <vector>

#define X first
#define Y second
#define PB push_back

using namespace std;

const int N = 5e5 + 500;

int c[N], L[N], R[N], ima[N], tL[N], tR[N], C[N];
vector < int > mogu[N];

inline void clean(int l,int r){
	for(int i = l;i < r;i++){
		for(int x : mogu[i])
			ima[x] = 0;
	}
}

inline void ubaci(int i){
	for(int x : mogu[i])
		ima[x] = 1;
}

inline void siri(int l,int r, int &cL, int &cR){
	for(;;){
		if(cL > l && ima[C[cL - 1]]){
			cL--; 
			if(cL != l) 
				ubaci(cL - 1);
			continue;
		}
		if(cR < r && ima[C[cR + 1]]){
			cR++;
			if(cR != r) 
				ubaci(cR);
			continue;
		}
		break;
	}
}

int n, q;

int main(){
	scanf("%d", &n);
	for(int i = 1;i < n;i++)
		scanf("%d", C + i);
	for(int i = 0;i < n;i++){
		int kol; scanf("%d", &kol);
		for(;kol--;){
			int x; scanf("%d", &x);
			mogu[i].PB(x);
		}
	}
	scanf("%d", &q);
	for(;q--;){
		int x, y; scanf("%d%d", &x, &y); x--, y--;
		int ll = x + 1, rr = x;
		ubaci(x);
		siri(0, n, ll, rr);
		printf((ll - 1 <= y && y <= rr) ? "YES\n" : "NO\n");
		clean(0, n);
	}
}

Compilation message

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", C + i);
   ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:52:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int kol; scanf("%d", &kol);
            ~~~~~^~~~~~~~~~~~
long_mansion.cpp:54:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x; scanf("%d", &x);
           ~~~~~^~~~~~~~~~
long_mansion.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:60:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y); x--, y--;
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 12160 KB Output is correct
2 Correct 159 ms 12288 KB Output is correct
3 Correct 221 ms 12408 KB Output is correct
4 Correct 98 ms 12280 KB Output is correct
5 Correct 183 ms 12256 KB Output is correct
6 Correct 109 ms 12288 KB Output is correct
7 Correct 91 ms 12408 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 12160 KB Output is correct
2 Correct 159 ms 12288 KB Output is correct
3 Correct 221 ms 12408 KB Output is correct
4 Correct 98 ms 12280 KB Output is correct
5 Correct 183 ms 12256 KB Output is correct
6 Correct 109 ms 12288 KB Output is correct
7 Correct 91 ms 12408 KB Output is correct
8 Execution timed out 3088 ms 14256 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3083 ms 16504 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 12160 KB Output is correct
2 Correct 159 ms 12288 KB Output is correct
3 Correct 221 ms 12408 KB Output is correct
4 Correct 98 ms 12280 KB Output is correct
5 Correct 183 ms 12256 KB Output is correct
6 Correct 109 ms 12288 KB Output is correct
7 Correct 91 ms 12408 KB Output is correct
8 Execution timed out 3088 ms 14256 KB Time limit exceeded
9 Halted 0 ms 0 KB -