oj.uz

답안 #433744

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
433744 2021-06-20T10:14:53 Z JeanBombeur 가로등 (APIO19_street_lamps) C++17
0 / 100
 611 ms 146260 KB 

    #include <iostream>
    #include <cstdio>
    #include <vector>
    using namespace std;
     
    //   <|°_°|>
     
    const int MAX_LAMPES = (300 * 1000 + 1);
    const int TAILLE_ARBRE = (1 << 19);
     
    struct node {
    	int left, right, val = 1;
    };
     
    int State[MAX_LAMPES];
     
    char Mot[MAX_LAMPES + 1];
     
    node Tree[MAX_LAMPES * 20];
    int sz = 1;
     
    int Racine[MAX_LAMPES];
     
    int nbLampes, nbRequetes;
     
    int Copy(int a, int &b) {
    	Tree[sz] = Tree[a];
    	return b = sz ++;
    }
     
    int MakeRoot(int id) {
    	return Copy(Racine[id - 1], Racine[id]);
    }
     
    void Push(int noeud, int gauche, int droite, int target, int add) {
    	if (droite - gauche == 1)
    	{
    		Tree[noeud].val = add;
    		return;
    	}
    	int mid = (gauche + droite) / 2;
    	if (target < mid)
    		Push(Copy(Tree[noeud].left, Tree[noeud].left), gauche, mid, target, add);
    	else
    		Push(Copy(Tree[noeud].right, Tree[noeud].right), mid, droite, target, add);
    	Tree[noeud].val = min(Tree[Tree[noeud].left].val, Tree[Tree[noeud].right].val);
    	return;
    }
     
    int GetMin(int noeud, int gauche, int droite, int inf, int sup) {
    	if (gauche >= sup || droite <= inf)
    		return 1;
    	if (gauche >= inf && droite <= sup)
    		return Tree[noeud].val;
    	int mid = (gauche + droite) / 2;
    	return min(GetMin(Tree[noeud].left, gauche, mid, inf, sup), GetMin(Tree[noeud].right, mid, droite, inf, sup));
    }
     
    void Read() {
    	scanf("%d %d", &nbLampes, &nbRequetes);
    	scanf("%s", Mot);
    	for (int i = 0; i < nbLampes; i ++)
    	{
    		State[i] = Mot[i] == '1';
    		Push(0, 0, TAILLE_ARBRE, i, State[i]);
    	}
    	return;
    }
     
    void Solve() {
    	for (int i = 1; i <= nbRequetes; i ++)
    	{
    		Racine[i] = MakeRoot(i);
    		int a, b;
    		scanf("%s %d", Mot, &a);
    		a --;
    		if (Mot[0] == 't')
    		{
    			Push(Racine[i], 0, TAILLE_ARBRE, a, 1);
    		}
    		else
    		{
    			scanf("%d", &b);
    			b --;
    			int ans = -1;
    			for (int j = (1 << 18); j > 0; j /= 2)
    			{
    				if (ans + j < i && GetMin(Racine[ans + j], 0, TAILLE_ARBRE, a, b) == 0)
    					ans += j;
    			}
    			printf("%d\n", i - (++ ans));
    		}
    	}
    	return;
    }
     
    int main() {
    	Read();
    	Solve();
    	return 0;
    }

Compilation message

street_lamps.cpp: In function 'void Read()':
street_lamps.cpp:62:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |      scanf("%d %d", &nbLampes, &nbRequetes);
      |      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:63:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |      scanf("%s", Mot);
      |      ~~~~~^~~~~~~~~~~
street_lamps.cpp: In function 'void Solve()':
street_lamps.cpp:77:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |       scanf("%s %d", Mot, &a);
      |       ~~~~~^~~~~~~~~~~~~~~~~~
street_lamps.cpp:85:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |        scanf("%d", &b);
      |        ~~~~~^~~~~~~~~~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 35 ms 70728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 611 ms 73048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 70688 KB Output is correct
2 Correct 35 ms 70732 KB Output is correct
3 Correct 34 ms 70744 KB Output is correct
4 Correct 35 ms 70792 KB Output is correct
5 Runtime error 228 ms 146260 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 70692 KB Output is correct
2 Incorrect 33 ms 70660 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 35 ms 70728 KB Output isn't correct
2 Halted 0 ms 0 KB -